<!DOCTYPE html>












  


<html class="theme-next mist use-motion" lang="zh-CN">
<head>
  <meta charset="UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=edge" />
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=2"/>
<meta name="theme-color" content="#222">



  
  
  <link rel="stylesheet" href="/lib/needsharebutton/needsharebutton.css">




  
  
    
    
  <script src="/lib/pace/pace.min.js?v=1.0.2"></script>
  <link href="/lib/pace/pace-theme-minimal.min.css?v=1.0.2" rel="stylesheet">







<meta http-equiv="Cache-Control" content="no-transform" />
<meta http-equiv="Cache-Control" content="no-siteapp" />
















  
  
  <link href="/lib/fancybox/source/jquery.fancybox.css?v=2.1.5" rel="stylesheet" type="text/css" />







<link href="/lib/font-awesome/css/font-awesome.min.css?v=4.6.2" rel="stylesheet" type="text/css" />

<link href="/css/main.css?v=6.3.0" rel="stylesheet" type="text/css" />


  <link rel="apple-touch-icon" sizes="180x180" href="/avatar.ico?v=6.3.0">


  <link rel="icon" type="image/png" sizes="32x32" href="/avatar.ico?v=6.3.0">


  <link rel="icon" type="image/png" sizes="16x16" href="/avatar.ico?v=6.3.0">


  <link rel="mask-icon" href="/avatar.ico?v=6.3.0" color="#222">









<script type="text/javascript" id="hexo.configurations">
  var NexT = window.NexT || {};
  var CONFIG = {
    root: '/',
    scheme: 'Mist',
    version: '6.3.0',
    sidebar: {"position":"left","display":"always","offset":12,"b2t":false,"scrollpercent":true,"onmobile":false},
    fancybox: true,
    fastclick: false,
    lazyload: false,
    tabs: true,
    motion: {"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},
    algolia: {
      applicationID: '',
      apiKey: '',
      indexName: '',
      hits: {"per_page":10},
      labels: {"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}
    }
  };
</script>


  




  <meta name="description" content="本处难度分档以个人实力为参照系难度1：半小时内想出，半小时内ac难度2：半小时想不出，看题解，服气难度3：半小时想不出，看题解，ac后依然觉得难度很大  另外，由于追进度，对于coding部分比较有自信的题目，不再具体实现">
<meta name="keywords" content="算法竞赛进阶指南">
<meta property="og:type" content="article">
<meta property="og:title" content="【训练】算法竞赛进阶指南-6图论 32题">
<meta property="og:url" content="http://zory.cf/posts/6259.html">
<meta property="og:site_name" content="Zory的个人博客">
<meta property="og:description" content="本处难度分档以个人实力为参照系难度1：半小时内想出，半小时内ac难度2：半小时想不出，看题解，服气难度3：半小时想不出，看题解，ac后依然觉得难度很大  另外，由于追进度，对于coding部分比较有自信的题目，不再具体实现">
<meta property="og:locale" content="zh-CN">
<meta property="og:image" content="http://zory.cf/images/算法竞赛进阶指南/6图论.png">
<meta property="og:image" content="http://zory.cf/images/算法竞赛进阶指南/走廊泼水节.png">
<meta property="og:updated_time" content="2018-09-18T07:01:15.702Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="【训练】算法竞赛进阶指南-6图论 32题">
<meta name="twitter:description" content="本处难度分档以个人实力为参照系难度1：半小时内想出，半小时内ac难度2：半小时想不出，看题解，服气难度3：半小时想不出，看题解，ac后依然觉得难度很大  另外，由于追进度，对于coding部分比较有自信的题目，不再具体实现">
<meta name="twitter:image" content="http://zory.cf/images/算法竞赛进阶指南/6图论.png">






  <link rel="canonical" href="http://zory.cf/posts/6259.html"/>



<script type="text/javascript" id="page.configurations">
  CONFIG.page = {
    sidebar: "",
  };
</script>

  <title>【训练】算法竞赛进阶指南-6图论 32题 | Zory的个人博客</title>
  






  <script type="text/javascript">
    var _hmt = _hmt || [];
    (function() {
      var hm = document.createElement("script");
      hm.src = "https://hm.baidu.com/hm.js?6c38ba8648d29103b8d122f998787d71";
      var s = document.getElementsByTagName("script")[0];
      s.parentNode.insertBefore(hm, s);
    })();
  </script>




  <noscript>
  <style type="text/css">
    .use-motion .motion-element,
    .use-motion .brand,
    .use-motion .menu-item,
    .sidebar-inner,
    .use-motion .post-block,
    .use-motion .pagination,
    .use-motion .comments,
    .use-motion .post-header,
    .use-motion .post-body,
    .use-motion .collection-title { opacity: initial; }

    .use-motion .logo,
    .use-motion .site-title,
    .use-motion .site-subtitle {
      opacity: initial;
      top: initial;
    }

    .use-motion {
      .logo-line-before i { left: initial; }
      .logo-line-after i { right: initial; }
    }
  </style>
</noscript>

</head>

<body itemscope itemtype="http://schema.org/WebPage" lang="zh-CN">

  
  
    
  

  <div class="container sidebar-position-left page-post-detail">
    <div class="headband"></div>

    <header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-wrapper">
  <div class="site-meta ">
    

    <div class="custom-logo-site-title">
      <a href="/" class="brand" rel="start">
        <span class="logo-line-before"><i></i></span>
        <span class="site-title">Zory的个人博客</span>
        <span class="logo-line-after"><i></i></span>
      </a>
    </div>
    
      
        <h1 class="site-subtitle" itemprop="description">人生即使不能走最短路，仍是连通图</h1>
      
    
  </div>

  <div class="site-nav-toggle">
    <button aria-label="切换导航栏">
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
    </button>
  </div>
</div>



<nav class="site-nav">
  
    <ul id="menu" class="menu">
      
        
        
        
          
          <li class="menu-item menu-item-home">
    <a href="/" rel="section">
      <i class="menu-item-icon fa fa-fw fa-home"></i> <br />首页Home</a>
  </li>
        
        
        
          
          <li class="menu-item menu-item-archives">
    <a href="/archives/" rel="section">
      <i class="menu-item-icon fa fa-fw fa-archive"></i> <br />历程Archives<span class="badge">354</span></a>
  </li>
        
        
        
          
          <li class="menu-item menu-item-categories">
    <a href="/categories/" rel="section">
      <i class="menu-item-icon fa fa-fw fa-th"></i> <br />分类Categories<span class="badge">4</span></a>
  </li>
        
        
        
          
          <li class="menu-item menu-item-tags">
    <a href="/tags/" rel="section">
      <i class="menu-item-icon fa fa-fw fa-tags"></i> <br />标签Tags<span class="badge">133</span></a>
  </li>
        
        
        
          
          <li class="menu-item menu-item-template">
    <a href="/categories/OI之路" rel="section">
      <i class="menu-item-icon fa fa-fw fa-telegram"></i> <br />OI之路</a>
  </li>
        
        
        
          
          <li class="menu-item menu-item-problems">
    <a href="/categories/刷题" rel="section">
      <i class="menu-item-icon fa fa-fw fa-list-alt"></i> <br />刷题Problems</a>
  </li>
        
        
        
          
          <li class="menu-item menu-item-friends">
    <a href="/friends/" rel="section">
      <i class="menu-item-icon fa fa-fw fa-user-circle"></i> <br />友链Friends</a>
  </li>
        
        
        
          
          <li class="menu-item menu-item-english">
    <a href="/English/" rel="section">
      <i class="menu-item-icon fa fa-fw fa-etsy"></i> <br />English知识体系</a>
  </li>
        
        
        
          
          <li class="menu-item menu-item-boutique">
    <a href="/tags/原创精华/" rel="section">
      <i class="menu-item-icon fa fa-fw fa-handshake-o"></i> <br />原创精华</a>
  </li>
        
        
        
          
          <li class="menu-item menu-item-top">
    <a href="/top/" rel="section">
      <i class="menu-item-icon fa fa-fw fa-signal"></i> <br />排行榜Hot</a>
  </li>

      
      
        <li class="menu-item menu-item-search">
          
            <a href="javascript:;" class="popup-trigger">
          
            
              <i class="menu-item-icon fa fa-search fa-fw"></i> <br />找文章强烈建议使用-搜索Search</a>
        </li>
      
    </ul>
  

  
    

  

  
    <div class="site-search">
      
  <div class="popup search-popup local-search-popup">
  <div class="local-search-header clearfix">
    <span class="search-icon">
      <i class="fa fa-search"></i>
    </span>
    <span class="popup-btn-close">
      <i class="fa fa-times-circle"></i>
    </span>
    <div class="local-search-input-wrapper">
      <input autocomplete="off"
             placeholder="这个搜索超级好用哦！找文章必备！" spellcheck="false"
             type="text" id="local-search-input">
    </div>
  </div>
  <div id="local-search-result"></div>
</div>



    </div>
  
</nav>



  



</div>
    </header>

    


    <main id="main" class="main">
      <div class="main-inner">
        <div class="content-wrap">
          
          <div id="content" class="content">
            

  <div id="posts" class="posts-expand">
    

  

  
  
  

  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://zory.cf/posts/6259.html">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="Zory">
      <meta itemprop="description" content="人生即使不能走最短路，仍是连通图">
      <meta itemprop="image" content="http://ouk2t1pgs.bkt.clouddn.com/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="Zory的个人博客">
    </span>

    
      <header class="post-header">

        
        
          <h2 class="post-title" itemprop="name headline">【训练】算法竞赛进阶指南-6图论 32题
              
            
          </h2>
        

        <div class="post-meta">
          <span class="post-time">

            
            
            

            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              

              
                
              

              <time title="创建于：2018-09-01 00:00:00" itemprop="dateCreated datePublished" datetime="2018-09-01T00:00:00+08:00">2018-09-01</time>
            

            
              

              
                
                <span class="post-meta-divider">|</span>
                

                <span class="post-meta-item-icon">
                  <i class="fa fa-calendar-check-o"></i>
                </span>
                
                  <span class="post-meta-item-text">更新于</span>
                
                <time title="修改于：2018-09-18 15:01:15" itemprop="dateModified" datetime="2018-09-18T15:01:15+08:00">2018-09-18</time>
              
            
          </span>

          
            <span class="post-category" >
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing"><a href="/categories/刷题/" itemprop="url" rel="index"><span itemprop="name">刷题</span></a></span>

                
                
              
            </span>
          

          
            
              <span class="post-comments-count">
                <span class="post-meta-divider">|</span>
                <span class="post-meta-item-icon">
                  <i class="fa fa-comment-o"></i>
                </span>
                <a href="/posts/6259.html#comments" itemprop="discussionUrl">
                  <span class="post-meta-item-text">评论：</span> <span class="post-comments-count valine-comment-count" data-xid="/posts/6259.html" itemprop="commentCount"></span>
                </a>
              </span>
            
          

          
          
             <span id="/posts/6259.html" class="leancloud_visitors" data-flag-title="【训练】算法竞赛进阶指南-6图论 32题">
               <span class="post-meta-divider">|</span>
               <span class="post-meta-item-icon">
                 <i class="fa fa-eye"></i>
               </span>
               
                 <span class="post-meta-item-text">热度：</span>
               
                 <span class="leancloud-visitors-count"></span>
             </span>
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        <p>本处难度分档以个人实力为参照系<br>难度1：半小时内想出，半小时内ac<br>难度2：半小时想不出，看题解，服气<br>难度3：半小时想不出，看题解，ac后依然觉得难度很大</p>
<p><img src="../images/算法竞赛进阶指南/6图论.png" alt=""></p>
<p>另外，由于追进度，对于coding部分比较有自信的题目，不再具体实现</p>
<a id="more"></a>
<h2 id="0x60-图论"><a href="#0x60-图论" class="headerlink" title="0x60 图论"></a>0x60 图论</h2><p><a href="http://contest-hunter.org:83/contest/0x60%E3%80%8C%E5%9B%BE%E8%AE%BA%E3%80%8D%E4%BE%8B%E9%A2%98" target="_blank" rel="noopener">部分题目</a></p>
<h3 id="1-poj3662-Telephone-Lines"><a href="#1-poj3662-Telephone-Lines" class="headerlink" title="1 poj3662 Telephone Lines"></a>1 poj3662 Telephone Lines</h3><p>8.29 难度2<br><div><div class="fold_hider"><div class="close hider_title">请先思考后再展开</div></div><div class="fold">
<p>找出一条从1到n的路径，上面第k+1大的那条边，权值最小<br>好弱啊第一题就不会做，天天看题解……</p>
<p>最小化除了前面k个以外的最大值，二分答案<br>把所有长度在mid以内的边看做0，否则1<br>跑一次最短路，如果花费在k以内，意味着可行<br>代码略</p>

</div></div></p>
<h3 id="2-noip2009-最优贸易"><a href="#2-noip2009-最优贸易" class="headerlink" title="2 noip2009 最优贸易"></a>2 noip2009 最优贸易</h3><p>8.29 难度2<br><div><div class="fold_hider"><div class="close hider_title">请先思考后再展开</div></div><div class="fold">
<p><a href="b656,html">曾经做过</a></p>

</div></div></p>
<h3 id="3-Usaco2011-Jan-Gold-道路和航线"><a href="#3-Usaco2011-Jan-Gold-道路和航线" class="headerlink" title="3 Usaco2011 Jan Gold 道路和航线"></a>3 Usaco2011 Jan Gold 道路和航线</h3><p>8.29 难度2<br><div><div class="fold_hider"><div class="close hider_title">请先思考后再展开</div></div><div class="fold">
<p>这道题挺有意思的，本来以为是裸题想跳的，看到lyd说spfa会tle，就不想以身试法了<br>（网上说加上slf就好了……不过本着锻炼思维的理念，学习一下正解）<br>因为题目保证航线没有环，本来以为这仅仅是保证没有负环，<br>没想到这还是一个突破口（还有就是道路都是双向的这个性质）</p>
<p>如果只加入双向边，那么就会形成多个联通块<br>如果缩点后再加入单向航线，图会形成一个有向无环图，是可以通过拓扑得到最短路的<br>不过具体而言，不能真的缩点，因为需要具体得出每个点的最短路<br>大致上就是沿着负权边找到各个联通块，以拓扑为框架跳来跳去</p>
<p>具体的话有个细节：<br>就是有可能st所在的联通块，入度不为0<br>或者可能出了st联通块外，还有其他入度不为0的联通块<br>所以还是要按照平常拓扑那样，把所有入度为0的加入栈<br>不过为了防止，单源最短路被扰乱，应该先把st联通块的dis置0，这样无论如何也没法更新掉了<br>然后其他联通块的inf也应该设置大一点，这样即使被更新，也是一个很大的值<br>然后输出no path的时候，不能只是和inf比较，因为可能曾经被更新，<br>要看它是否明显超过理论正常最大距离( $T \times 10000=250000000$ )，设为0x3f3f3f3f就够了<br><figure class="highlight cpp"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div><div class="line">25</div><div class="line">26</div><div class="line">27</div><div class="line">28</div><div class="line">29</div><div class="line">30</div><div class="line">31</div><div class="line">32</div><div class="line">33</div><div class="line">34</div><div class="line">35</div><div class="line">36</div><div class="line">37</div><div class="line">38</div><div class="line">39</div><div class="line">40</div><div class="line">41</div><div class="line">42</div><div class="line">43</div><div class="line">44</div><div class="line">45</div><div class="line">46</div><div class="line">47</div><div class="line">48</div><div class="line">49</div><div class="line">50</div><div class="line">51</div><div class="line">52</div><div class="line">53</div><div class="line">54</div><div class="line">55</div><div class="line">56</div><div class="line">57</div><div class="line">58</div><div class="line">59</div><div class="line">60</div><div class="line">61</div><div class="line">62</div><div class="line">63</div><div class="line">64</div><div class="line">65</div><div class="line">66</div><div class="line">67</div><div class="line">68</div><div class="line">69</div><div class="line">70</div><div class="line">71</div><div class="line">72</div><div class="line">73</div><div class="line">74</div><div class="line">75</div><div class="line">76</div><div class="line">77</div><div class="line">78</div><div class="line">79</div><div class="line">80</div><div class="line">81</div><div class="line">82</div><div class="line">83</div><div class="line">84</div><div class="line">85</div><div class="line">86</div><div class="line">87</div><div class="line">88</div><div class="line">89</div><div class="line">90</div><div class="line">91</div><div class="line">92</div><div class="line">93</div><div class="line">94</div><div class="line">95</div><div class="line">96</div><div class="line">97</div><div class="line">98</div><div class="line">99</div><div class="line">100</div><div class="line">101</div><div class="line">102</div><div class="line">103</div><div class="line">104</div><div class="line">105</div><div class="line">106</div><div class="line">107</div><div class="line">108</div><div class="line">109</div><div class="line">110</div><div class="line">111</div><div class="line">112</div><div class="line">113</div><div class="line">114</div><div class="line">115</div><div class="line">116</div><div class="line">117</div><div class="line">118</div><div class="line">119</div><div class="line">120</div><div class="line">121</div><div class="line">122</div><div class="line">123</div><div class="line">124</div><div class="line">125</div><div class="line">126</div><div class="line">127</div><div class="line">128</div></pre></td><td class="code"><pre><div class="line"><span class="comment">//Zory-2018</span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;cmath&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;cstdio&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;cstring&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;cstdlib&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;map&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;set&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;queue&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;deque&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;bitset&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;vector&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;algorithm&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;iostream&gt;</span></span></div><div class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</div><div class="line"></div><div class="line"><span class="keyword">namespace</span> mine</div><div class="line">&#123;</div><div class="line">    <span class="keyword">typedef</span> <span class="keyword">long</span> <span class="keyword">long</span> ll;</div><div class="line">    <span class="meta">#<span class="meta-keyword">define</span> double long double</span></div><div class="line">    <span class="keyword">const</span> <span class="keyword">int</span> MAX_N=<span class="number">31000</span>,MAX_M=<span class="number">160000</span>;</div><div class="line">    <span class="keyword">const</span> ll INF=(<span class="number">1l</span>l&lt;&lt;<span class="number">60</span>);</div><div class="line"></div><div class="line">    <span class="keyword">int</span> n;</div><div class="line"></div><div class="line">    <span class="keyword">struct</span> Nod</div><div class="line">    &#123;</div><div class="line">        <span class="keyword">int</span> hou;</div><div class="line">        ll dis;</div><div class="line">        <span class="keyword">int</span> uni;</div><div class="line">        Nod()</div><div class="line">        &#123;</div><div class="line">            uni=hou=<span class="number">0</span>;</div><div class="line">            dis=INF;</div><div class="line">        &#125;</div><div class="line">    &#125;p[MAX_N];</div><div class="line">    <span class="keyword">struct</span> Edge</div><div class="line">    &#123;</div><div class="line">        <span class="keyword">int</span> y,c,g;</div><div class="line">    &#125;e[MAX_M];</div><div class="line">    <span class="keyword">int</span> ln=<span class="number">0</span>;</div><div class="line">    <span class="function"><span class="keyword">void</span> <span class="title">ins</span><span class="params">(<span class="keyword">int</span> x,<span class="keyword">int</span> y,<span class="keyword">int</span> c)</span></div><div class="line">    </span>&#123;</div><div class="line">        e[++ln]=(Edge)&#123;y,c,p[x].hou&#125;;</div><div class="line">        p[x].hou=ln;</div><div class="line">    &#125;</div><div class="line"></div><div class="line">    <span class="keyword">int</span> deg[MAX_N];</div><div class="line">    <span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; vt[MAX_N];</div><div class="line">    <span class="function"><span class="keyword">void</span> <span class="title">dfs</span><span class="params">(<span class="keyword">int</span> x,<span class="keyword">int</span> now)</span></div><div class="line">    </span>&#123;</div><div class="line">        p[x].uni=now;vt[now].push_back(x);</div><div class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> k=p[x].hou;k&gt;<span class="number">0</span>;k=e[k].g) <span class="keyword">if</span>(p[e[k].y].uni==<span class="number">0</span>) dfs(e[k].y,now);</div><div class="line">    &#125;</div><div class="line"></div><div class="line">    <span class="keyword">struct</span> Que</div><div class="line">    &#123;</div><div class="line">        ll d;</div><div class="line">        <span class="keyword">int</span> x;</div><div class="line">        <span class="keyword">friend</span> <span class="keyword">bool</span> <span class="keyword">operator</span> &lt; (Que a,Que b) &#123;<span class="keyword">return</span> a.d&gt;b.d;&#125;</div><div class="line">    &#125;;</div><div class="line">    <span class="keyword">int</span> sta[MAX_N],top=<span class="number">0</span>;</div><div class="line">    priority_queue&lt;Que&gt; q;</div><div class="line">    <span class="function"><span class="keyword">void</span> <span class="title">solve</span><span class="params">(<span class="keyword">int</span> st)</span></div><div class="line">    </span>&#123;</div><div class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;vt[p[st].uni].size();i++)</div><div class="line">            p[vt[p[st].uni][i]].dis=<span class="number">0</span>;<span class="comment">//确保不会被，st无法到达的块更新</span></div><div class="line"></div><div class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=n;i++) <span class="keyword">if</span>(vt[i].size()&gt;<span class="number">0</span> and deg[i]==<span class="number">0</span>) sta[++top]=i;</div><div class="line">        <span class="keyword">while</span>(top&gt;<span class="number">0</span>)<span class="comment">//topsort</span></div><div class="line">        &#123;</div><div class="line">            <span class="keyword">int</span> t=sta[top--];</div><div class="line">            <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;vt[t].size();i++)</div><div class="line">            &#123;</div><div class="line">                <span class="keyword">int</span> x=vt[t][i];</div><div class="line">                <span class="keyword">if</span>(t==p[st].uni and x!=st) p[x].dis=INF;<span class="comment">//debug 漏了</span></div><div class="line">                q.push((Que)&#123;p[x].dis,x&#125;);</div><div class="line">            &#125;</div><div class="line"></div><div class="line">            <span class="keyword">while</span>(!q.empty())<span class="comment">//dijkstra</span></div><div class="line">            &#123;</div><div class="line">                Que now=q.top();q.pop();</div><div class="line">                <span class="keyword">int</span> x=now.x;<span class="keyword">if</span>(now.d!=p[x].dis) <span class="keyword">continue</span>;<span class="comment">//delete</span></div><div class="line"></div><div class="line">                <span class="keyword">for</span>(<span class="keyword">int</span> k=p[x].hou;k&gt;<span class="number">0</span>;k=e[k].g)</div><div class="line">                &#123;</div><div class="line">                    <span class="keyword">int</span> y=e[k].y;</div><div class="line"></div><div class="line">                    <span class="keyword">if</span>(p[y].dis&gt;p[x].dis+e[k].c)</div><div class="line">                    &#123;</div><div class="line">                        p[y].dis=p[x].dis+e[k].c;</div><div class="line">                        <span class="keyword">if</span>(p[y].uni==p[x].uni) q.push((Que)&#123;p[y].dis,y&#125;);</div><div class="line">                    &#125;</div><div class="line"></div><div class="line">                    <span class="keyword">if</span>(p[y].uni!=p[x].uni)</div><div class="line">                    &#123;</div><div class="line">                        deg[p[y].uni]--;</div><div class="line">                        <span class="keyword">if</span>(deg[p[y].uni]==<span class="number">0</span>) sta[++top]=p[y].uni;</div><div class="line">                    &#125;</div><div class="line">                &#125;</div><div class="line">            &#125;</div><div class="line">        &#125;</div><div class="line">    &#125;</div><div class="line"></div><div class="line">    <span class="function"><span class="keyword">void</span> <span class="title">main</span><span class="params">()</span></div><div class="line">    </span>&#123;</div><div class="line">        <span class="keyword">int</span> ma,mb,st;<span class="built_in">scanf</span>(<span class="string">"%d%d%d%d"</span>,&amp;n,&amp;ma,&amp;mb,&amp;st);</div><div class="line">        <span class="keyword">while</span>(ma--)</div><div class="line">        &#123;</div><div class="line">            <span class="keyword">int</span> x,y,c;<span class="built_in">scanf</span>(<span class="string">"%d%d%d"</span>,&amp;x,&amp;y,&amp;c);</div><div class="line">            ins(x,y,c);ins(y,x,c);</div><div class="line">        &#125;</div><div class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=n;i++) <span class="keyword">if</span>(p[i].uni==<span class="number">0</span>) dfs(i,i);</div><div class="line">        <span class="keyword">while</span>(mb--)</div><div class="line">        &#123;</div><div class="line">            <span class="keyword">int</span> x,y,c;<span class="built_in">scanf</span>(<span class="string">"%d%d%d"</span>,&amp;x,&amp;y,&amp;c);</div><div class="line">            ins(x,y,c);<span class="keyword">if</span>(p[x].uni!=p[y].uni) deg[p[y].uni]++;</div><div class="line">        &#125;</div><div class="line">        solve(st);</div><div class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=n;i++)</div><div class="line">            <span class="keyword">if</span>(p[i].dis&gt;<span class="number">0x3f3f3f3f</span>) <span class="built_in">puts</span>(<span class="string">"NO PATH"</span>);</div><div class="line">            <span class="keyword">else</span> <span class="built_in">printf</span>(<span class="string">"%lld\n"</span>,p[i].dis);</div><div class="line">    &#125;</div><div class="line">&#125;;</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></div><div class="line"></span>&#123;</div><div class="line">    mine::main();</div><div class="line">&#125;</div></pre></td></tr></table></figure></p>

</div></div></p>
<h3 id="4-poj1734-Sightseeing-trip"><a href="#4-poj1734-Sightseeing-trip" class="headerlink" title="4 poj1734 Sightseeing trip"></a>4 poj1734 Sightseeing trip</h3><p>8.29 难度2<br><div><div class="fold_hider"><div class="close hider_title">请先思考后再展开</div></div><div class="fold">
<p><a href="a73f.html">floyd找最小环</a><br><figure class="highlight cpp"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div><div class="line">25</div><div class="line">26</div><div class="line">27</div><div class="line">28</div><div class="line">29</div><div class="line">30</div><div class="line">31</div><div class="line">32</div><div class="line">33</div><div class="line">34</div><div class="line">35</div><div class="line">36</div><div class="line">37</div><div class="line">38</div><div class="line">39</div><div class="line">40</div><div class="line">41</div><div class="line">42</div><div class="line">43</div><div class="line">44</div><div class="line">45</div><div class="line">46</div><div class="line">47</div><div class="line">48</div><div class="line">49</div><div class="line">50</div><div class="line">51</div><div class="line">52</div><div class="line">53</div><div class="line">54</div><div class="line">55</div><div class="line">56</div><div class="line">57</div><div class="line">58</div><div class="line">59</div><div class="line">60</div><div class="line">61</div><div class="line">62</div><div class="line">63</div><div class="line">64</div><div class="line">65</div><div class="line">66</div><div class="line">67</div><div class="line">68</div><div class="line">69</div><div class="line">70</div><div class="line">71</div><div class="line">72</div></pre></td><td class="code"><pre><div class="line"><span class="comment">//Zory-2018</span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;cmath&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;cstdio&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;cstring&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;cstdlib&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;map&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;set&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;queue&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;deque&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;bitset&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;vector&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;algorithm&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;iostream&gt;</span></span></div><div class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</div><div class="line"></div><div class="line"><span class="keyword">namespace</span> mine</div><div class="line">&#123;</div><div class="line">    <span class="keyword">typedef</span> <span class="keyword">long</span> <span class="keyword">long</span> ll;</div><div class="line">    <span class="meta">#<span class="meta-keyword">define</span> double long double</span></div><div class="line">    <span class="keyword">const</span> <span class="keyword">int</span> MAX_N=<span class="number">110</span>;</div><div class="line">    <span class="keyword">const</span> <span class="keyword">int</span> INF=<span class="number">0x3f3f3f3f</span>;</div><div class="line"></div><div class="line">    <span class="keyword">int</span> ans[MAX_N],ln;</div><div class="line">    <span class="keyword">int</span> fm[MAX_N][MAX_N];</div><div class="line">    <span class="keyword">int</span> dis[MAX_N][MAX_N],a[MAX_N][MAX_N];</div><div class="line">    <span class="function"><span class="keyword">void</span> <span class="title">getans</span><span class="params">(<span class="keyword">int</span> x,<span class="keyword">int</span> y)</span></div><div class="line">    </span>&#123;</div><div class="line">        <span class="keyword">if</span>(fm[x][y]&lt;<span class="number">0</span>) &#123;ans[++ln]=x;<span class="keyword">return</span>;&#125;</div><div class="line">        <span class="keyword">int</span> k=fm[x][y];</div><div class="line">        getans(x,k);getans(k,y);</div><div class="line">    &#125;</div><div class="line">    <span class="function"><span class="keyword">void</span> <span class="title">main</span><span class="params">()</span></div><div class="line">    </span>&#123;</div><div class="line">        <span class="keyword">int</span> n,m;<span class="built_in">scanf</span>(<span class="string">"%d%d"</span>,&amp;n,&amp;m);</div><div class="line">        <span class="built_in">memset</span>(a,<span class="number">63</span>,<span class="keyword">sizeof</span> a);</div><div class="line">        <span class="built_in">memset</span>(fm,<span class="number">0</span>,<span class="keyword">sizeof</span> fm);</div><div class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=n;i++) a[i][i]=<span class="number">0</span>;</div><div class="line">        <span class="keyword">while</span>(m--)</div><div class="line">        &#123;</div><div class="line">            <span class="keyword">int</span> x,y,c;<span class="built_in">scanf</span>(<span class="string">"%d%d%d"</span>,&amp;x,&amp;y,&amp;c);</div><div class="line">            <span class="keyword">if</span>(c&lt;a[x][y]) a[x][y]=a[y][x]=c,fm[x][y]=fm[y][x]=<span class="number">-1</span>;</div><div class="line">        &#125;</div><div class="line">        <span class="built_in">memcpy</span>(dis,a,<span class="keyword">sizeof</span> a);</div><div class="line"></div><div class="line">        <span class="keyword">int</span> mi=INF;</div><div class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> k=<span class="number">1</span>;k&lt;=n;k++)</div><div class="line">        &#123;</div><div class="line">            <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;k;i++)</div><div class="line">                <span class="keyword">for</span>(<span class="keyword">int</span> j=i+<span class="number">1</span>;j&lt;k;j++)</div><div class="line">                &#123;</div><div class="line">                    ll tmp=(ll)dis[i][j]+a[j][k]+a[k][i];<span class="comment">//debug 爆int</span></div><div class="line">                    <span class="keyword">if</span>(mi&gt;tmp)</div><div class="line">                    &#123;</div><div class="line">                        mi=tmp;</div><div class="line">                        ln=<span class="number">0</span>;getans(i,j);ans[++ln]=j;ans[++ln]=k;</div><div class="line">                    &#125;</div><div class="line">                &#125;</div><div class="line"></div><div class="line">            <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=n;i++)</div><div class="line">                <span class="keyword">for</span>(<span class="keyword">int</span> j=<span class="number">1</span>;j&lt;=n;j++) <span class="keyword">if</span>(i!=j)</div><div class="line">                    <span class="keyword">if</span>(dis[i][j]&gt;dis[i][k]+dis[k][j])</div><div class="line">                        dis[i][j]=dis[i][k]+dis[k][j],fm[i][j]=k;</div><div class="line">        &#125;</div><div class="line">        <span class="keyword">if</span>(mi==INF) <span class="built_in">puts</span>(<span class="string">"No solution."</span>);<span class="comment">//神tm漏了一个点……</span></div><div class="line">        <span class="keyword">else</span> <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=ln;i++) <span class="built_in">printf</span>(<span class="string">"%d "</span>,ans[i]);</div><div class="line">    &#125;</div><div class="line">&#125;;</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></div><div class="line"></span>&#123;</div><div class="line">    mine::main();</div><div class="line">&#125;</div></pre></td></tr></table></figure></p>

</div></div></p>
<h3 id="5-6201-走廊泼水节"><a href="#5-6201-走廊泼水节" class="headerlink" title="5 6201 走廊泼水节"></a>5 6201 走廊泼水节</h3><p>8.29 难度2<br><div><div class="fold_hider"><div class="close hider_title">请先思考后再展开</div></div><div class="fold">
<p>这道题设计得很好<br>个人很喜欢这种，对看似简单、经典的算法，推陈出新地挖掘细节、原理的题目<br><del>结果就不会做了……</del></p>
<p>这道题从边的角度思考会简单一些<br>想到边，以及最小生成树，会想到kruskal<br>把所有边排序，然后关键就是“完全图中的边，是否跨树”<br>对于这一点我只能出个数据把自己的乱搞做法卡掉，但不知道怎么去解决</p>
<p>其实这条边什么时候会跨树呢？<br>盗lyd好图：<br><img src="../images/算法竞赛进阶指南/走廊泼水节.png" alt=""><br>是不是豁然开朗了？<br>模拟kruskal的过程，连接两个树之间的边，只会在这一次跨树<br>此时，他们的取值都应为z+1，个数则是 $Sx \times Sy-1$<br><figure class="highlight cpp"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div><div class="line">25</div><div class="line">26</div><div class="line">27</div><div class="line">28</div><div class="line">29</div><div class="line">30</div><div class="line">31</div><div class="line">32</div><div class="line">33</div><div class="line">34</div><div class="line">35</div><div class="line">36</div><div class="line">37</div><div class="line">38</div><div class="line">39</div><div class="line">40</div><div class="line">41</div><div class="line">42</div><div class="line">43</div><div class="line">44</div><div class="line">45</div><div class="line">46</div><div class="line">47</div><div class="line">48</div><div class="line">49</div><div class="line">50</div><div class="line">51</div><div class="line">52</div><div class="line">53</div><div class="line">54</div><div class="line">55</div><div class="line">56</div><div class="line">57</div></pre></td><td class="code"><pre><div class="line"><span class="comment">//Zory-2018</span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;cmath&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;cstdio&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;cstring&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;cstdlib&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;map&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;set&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;queue&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;deque&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;bitset&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;vector&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;algorithm&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;iostream&gt;</span></span></div><div class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</div><div class="line"></div><div class="line"><span class="keyword">namespace</span> mine</div><div class="line">&#123;</div><div class="line">    <span class="keyword">typedef</span> <span class="keyword">long</span> <span class="keyword">long</span> ll;</div><div class="line">    <span class="meta">#<span class="meta-keyword">define</span> double long double</span></div><div class="line">    <span class="keyword">const</span> <span class="keyword">int</span> MAX_N=<span class="number">6100</span>;</div><div class="line">    <span class="keyword">const</span> <span class="keyword">int</span> INF=<span class="number">0x3f3f3f3f</span>;</div><div class="line"></div><div class="line">    <span class="keyword">struct</span> Edge</div><div class="line">    &#123;</div><div class="line">        <span class="keyword">int</span> x,y,c;</div><div class="line">    &#125;e[MAX_N];</div><div class="line">    <span class="function"><span class="keyword">bool</span> <span class="title">cmp</span><span class="params">(Edge a,Edge b)</span> </span>&#123;<span class="keyword">return</span> a.c&lt;b.c;&#125;</div><div class="line"></div><div class="line">    <span class="keyword">int</span> fa[MAX_N],siz[MAX_N];</div><div class="line">    <span class="function"><span class="keyword">int</span> <span class="title">findfa</span><span class="params">(<span class="keyword">int</span> x)</span> </span>&#123;<span class="keyword">return</span> fa[x]=(x==fa[x]?x:findfa(fa[x]));&#125;</div><div class="line">    <span class="function"><span class="keyword">void</span> <span class="title">main</span><span class="params">()</span></div><div class="line">    </span>&#123;</div><div class="line">        <span class="keyword">int</span> T;<span class="built_in">scanf</span>(<span class="string">"%d"</span>,&amp;T);</div><div class="line">        <span class="keyword">while</span>(T--)</div><div class="line">        &#123;</div><div class="line">            <span class="keyword">int</span> n;<span class="built_in">scanf</span>(<span class="string">"%d"</span>,&amp;n);</div><div class="line">            <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=n;i++) fa[i]=i,siz[i]=<span class="number">1</span>;</div><div class="line">            <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=n<span class="number">-1</span>;i++) <span class="built_in">scanf</span>(<span class="string">"%d%d%d"</span>,&amp;e[i].x,&amp;e[i].y,&amp;e[i].c);</div><div class="line">            sort(e+<span class="number">1</span>,e+n<span class="number">-1</span>+<span class="number">1</span>,cmp);</div><div class="line"></div><div class="line">            ll ans=<span class="number">0</span>;</div><div class="line">            <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=n<span class="number">-1</span>;i++)</div><div class="line">            &#123;</div><div class="line">                <span class="keyword">int</span> x=e[i].x,y=e[i].y;</div><div class="line">                <span class="keyword">int</span> fx=findfa(x),fy=findfa(y);</div><div class="line">                ans+=ll(e[i].c+<span class="number">1</span>)*( (ll)siz[fx]*siz[fy]<span class="number">-1</span> );</div><div class="line">                <span class="keyword">if</span>(fx!=fy) fa[fx]=fy,siz[fy]+=siz[fx];<span class="comment">//merg</span></div><div class="line">            &#125;</div><div class="line">            <span class="built_in">printf</span>(<span class="string">"%lld\n"</span>,ans);</div><div class="line">        &#125;</div><div class="line">    &#125;</div><div class="line">&#125;;</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></div><div class="line"></span>&#123;</div><div class="line">    mine::main();</div><div class="line">&#125;</div></pre></td></tr></table></figure></p>

</div></div></p>
<h3 id="6-poj1639-Picnic-Planning"><a href="#6-poj1639-Picnic-Planning" class="headerlink" title="6 poj1639 Picnic Planning"></a>6 poj1639 Picnic Planning</h3><p>8.30 难度2<br><div><div class="fold_hider"><div class="close hider_title">请先思考后再展开</div></div><div class="fold">
<p>就是限制了根节点度数的最小生成树<br>先去除1节点，跑出每个节点的最小生成树，然后找最小的一条边连接上去<br>然后有可能可以对某个点x，去掉某条1到x的一条边，并连接x和1</p>

</div></div></p>
<h3 id="7-poj2728-Desert-King"><a href="#7-poj2728-Desert-King" class="headerlink" title="7 poj2728 Desert King"></a>7 poj2728 Desert King</h3><p>8.30 难度1<br><div><div class="fold_hider"><div class="close hider_title">请先思考后再展开</div></div><div class="fold">
<p>01分数规划+最小生成树<br>不过不知道为什么跑得很慢<br>log的大小，无论如何都是在100以内的，那么正常来说这道题就一亿，时限3s<br>个人觉得它非要卡二分我也没办法，Dinkelbach大概只是恰好快而已（毕竟那东西的复杂度很玄学）<br><figure class="highlight cpp"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div><div class="line">25</div><div class="line">26</div><div class="line">27</div><div class="line">28</div><div class="line">29</div><div class="line">30</div><div class="line">31</div><div class="line">32</div><div class="line">33</div><div class="line">34</div><div class="line">35</div><div class="line">36</div><div class="line">37</div><div class="line">38</div><div class="line">39</div><div class="line">40</div><div class="line">41</div><div class="line">42</div><div class="line">43</div><div class="line">44</div><div class="line">45</div><div class="line">46</div><div class="line">47</div><div class="line">48</div><div class="line">49</div><div class="line">50</div><div class="line">51</div><div class="line">52</div><div class="line">53</div><div class="line">54</div><div class="line">55</div><div class="line">56</div><div class="line">57</div><div class="line">58</div><div class="line">59</div><div class="line">60</div><div class="line">61</div><div class="line">62</div><div class="line">63</div><div class="line">64</div><div class="line">65</div><div class="line">66</div><div class="line">67</div><div class="line">68</div><div class="line">69</div><div class="line">70</div><div class="line">71</div><div class="line">72</div><div class="line">73</div><div class="line">74</div><div class="line">75</div><div class="line">76</div><div class="line">77</div><div class="line">78</div><div class="line">79</div><div class="line">80</div><div class="line">81</div><div class="line">82</div><div class="line">83</div><div class="line">84</div><div class="line">85</div><div class="line">86</div><div class="line">87</div><div class="line">88</div><div class="line">89</div><div class="line">90</div><div class="line">91</div><div class="line">92</div><div class="line">93</div><div class="line">94</div><div class="line">95</div><div class="line">96</div><div class="line">97</div><div class="line">98</div><div class="line">99</div><div class="line">100</div><div class="line">101</div><div class="line">102</div><div class="line">103</div><div class="line">104</div><div class="line">105</div><div class="line">106</div><div class="line">107</div></pre></td><td class="code"><pre><div class="line"><span class="comment">//Zory-2018</span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;cmath&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;cstdio&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;cstring&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;cstdlib&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;map&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;set&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;queue&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;deque&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;bitset&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;vector&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;algorithm&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;iostream&gt;</span></span></div><div class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</div><div class="line"></div><div class="line"><span class="keyword">namespace</span> mine</div><div class="line">&#123;</div><div class="line">    <span class="keyword">typedef</span> <span class="keyword">long</span> <span class="keyword">long</span> ll;</div><div class="line">    <span class="meta">#<span class="meta-keyword">define</span> double long double</span></div><div class="line">    <span class="keyword">const</span> <span class="keyword">int</span> MAX_N=<span class="number">1100</span>;</div><div class="line">    <span class="keyword">const</span> <span class="keyword">int</span> INF=<span class="number">0x3f3f3f3f</span>;</div><div class="line">    <span class="function"><span class="keyword">double</span> <span class="title">myabs</span><span class="params">(<span class="keyword">double</span> x)</span> </span>&#123;<span class="keyword">return</span> x&gt;<span class="number">0</span>?x:-x;&#125;</div><div class="line">    <span class="keyword">const</span> <span class="keyword">double</span> eps=<span class="number">1e-8</span>;</div><div class="line"></div><div class="line">    <span class="keyword">struct</span> Nod</div><div class="line">    &#123;</div><div class="line">        <span class="keyword">int</span> x,y;</div><div class="line">        <span class="keyword">int</span> h;</div><div class="line">    &#125;p[MAX_N];</div><div class="line">    <span class="function"><span class="keyword">double</span> <span class="title">dis</span><span class="params">(<span class="keyword">double</span> x1,<span class="keyword">double</span> y1,<span class="keyword">double</span> x2,<span class="keyword">double</span> y2)</span> </span>&#123;<span class="keyword">return</span> <span class="built_in">sqrt</span>( (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2) );&#125;</div><div class="line"></div><div class="line">    <span class="keyword">int</span> n;</div><div class="line">    <span class="keyword">double</span> L;</div><div class="line"></div><div class="line">    <span class="keyword">double</span> d[MAX_N],a[MAX_N][MAX_N],cst[MAX_N][MAX_N],ln[MAX_N][MAX_N];</div><div class="line">    <span class="keyword">bool</span> v[MAX_N];</div><div class="line">    <span class="function"><span class="keyword">bool</span> <span class="title">check</span><span class="params">()</span><span class="comment">//prim&lt;=0</span></div><div class="line">    </span>&#123;</div><div class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=n;i++) <span class="keyword">for</span>(<span class="keyword">int</span> j=<span class="number">1</span>;j&lt;=n;j++) a[i][j]=cst[i][j]-L*ln[i][j];</div><div class="line">        d[<span class="number">0</span>]=INF;d[<span class="number">1</span>]=<span class="number">0</span>;<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">2</span>;i&lt;=n;i++) d[i]=a[<span class="number">1</span>][i];</div><div class="line">        <span class="built_in">memset</span>(v,<span class="number">0</span>,<span class="keyword">sizeof</span> v);v[<span class="number">1</span>]=<span class="number">1</span>;</div><div class="line"></div><div class="line">        <span class="keyword">double</span> sum=<span class="number">0</span>;</div><div class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> cnt=<span class="number">1</span>;cnt&lt;=n<span class="number">-1</span>;cnt++)</div><div class="line">        &#123;</div><div class="line">            <span class="keyword">int</span> t=<span class="number">0</span>;<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=n;i++) <span class="keyword">if</span>(!v[i] and d[i]&lt;d[t]) t=i;</div><div class="line">            sum+=d[t];v[t]=<span class="number">1</span>;</div><div class="line">            <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=n;i++) <span class="keyword">if</span>(!v[i] and a[t][i]&lt;d[i]) d[i]=a[t][i];</div><div class="line">        &#125;</div><div class="line">        <span class="keyword">return</span> sum&lt;=eps;</div><div class="line">    &#125;</div><div class="line">    <span class="comment">/*</div><div class="line">    int m;</div><div class="line">    struct Edge</div><div class="line">    &#123;</div><div class="line">        int x,y;</div><div class="line">        double cst,ln;</div><div class="line">    &#125;e[MAX_N*MAX_N];</div><div class="line">    bool cmp(Edge a,Edge b) &#123;return a.cst-L*a.ln&lt;b.cst-L*b.ln;&#125;</div><div class="line">    int fa[MAX_N];</div><div class="line">    int findfa(int x) &#123;return fa[x]=(x==fa[x]?x:findfa(fa[x]));&#125;</div><div class="line">    bool check()//kruskal&lt;=0 沙茶了，完全图用kruskal……</div><div class="line">    &#123;</div><div class="line">        sort(e+1,e+m+1,cmp);</div><div class="line">        for(int i=1;i&lt;=n;i++) fa[i]=i;//debug</div><div class="line"></div><div class="line">        double sum=0;</div><div class="line">        for(int i=1;i&lt;=m;i++)</div><div class="line">        &#123;</div><div class="line">            int x=e[i].x,y=e[i].y;</div><div class="line">            int fx=findfa(x),fy=findfa(y);</div><div class="line">            if(fx!=fy)</div><div class="line">            &#123;</div><div class="line">                sum+=e[i].cst-L*e[i].ln;</div><div class="line">                fa[fx]=fy;</div><div class="line">            &#125;</div><div class="line">        &#125;</div><div class="line">        return sum&lt;=0;</div><div class="line">    &#125;*/</span></div><div class="line">    <span class="function"><span class="keyword">void</span> <span class="title">main</span><span class="params">()</span></div><div class="line">    </span>&#123;</div><div class="line">        <span class="keyword">while</span>(<span class="number">1</span>)</div><div class="line">        &#123;</div><div class="line">            <span class="built_in">scanf</span>(<span class="string">"%d"</span>,&amp;n);</div><div class="line">            <span class="keyword">if</span>(n==<span class="number">0</span>) <span class="keyword">break</span>;</div><div class="line"></div><div class="line">            <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=n;i++) <span class="built_in">scanf</span>(<span class="string">"%d%d%d"</span>,&amp;p[i].x,&amp;p[i].y,&amp;p[i].h);</div><div class="line">            <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=n;i++)</div><div class="line">                <span class="keyword">for</span>(<span class="keyword">int</span> j=<span class="number">1</span>;j&lt;=n;j++)</div><div class="line">                    cst[i][j]=myabs(p[i].h-p[j].h),ln[i][j]=dis(p[i].x,p[i].y,p[j].x,p[j].y);</div><div class="line"></div><div class="line">            <span class="keyword">double</span> l=<span class="number">0</span>,r=INF,ans=<span class="number">-1</span>;</div><div class="line">            <span class="keyword">while</span>(l&lt;=r+eps)</div><div class="line">            &#123;</div><div class="line">                L=(l+r)/<span class="number">2</span>;</div><div class="line">                <span class="keyword">if</span>(check()) ans=L,r=L-eps;</div><div class="line">                <span class="keyword">else</span> l=L+eps;</div><div class="line">            &#125;</div><div class="line">            <span class="built_in">printf</span>(<span class="string">"%.3lf\n"</span>,ans);</div><div class="line">        &#125;</div><div class="line">    &#125;</div><div class="line">&#125;;</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></div><div class="line"></span>&#123;</div><div class="line">    mine::main();</div><div class="line">&#125;</div></pre></td></tr></table></figure></p>

</div></div></p>
<h3 id="8-APIO2010-巡逻"><a href="#8-APIO2010-巡逻" class="headerlink" title="8 APIO2010 巡逻"></a>8 APIO2010 巡逻</h3><p>8.30 难度2<br><div><div class="fold_hider"><div class="close hider_title">请先思考后再展开</div></div><div class="fold">
<p>这道题的k=1、2，先从k=0入手<br>不难发现，每条边一定要经过两次（因为是树，一定会递归一次回溯一次），所以就是$2(n-1)$<br>对于k=1，加入一条新的边以后，一定出现了环，就不一定是两次了<br>同时，在这个环上，其他边都从经过两次变成了经过一次（例如题目中的a）<br>不难发现，此时答案为$2(n-1)-(直径长度-1)$</p>
<p>对于k=2的情况，稍微复杂了一些<br>如果产生的新的环，没有和原本的环重叠，那么同样是不用经过一次（例如题目中的b）<br>但是，如果重叠了（例如题目中的c），那么由于“新的边必须经过一次”这个限制，公共部分又变成了要经过两次</p>
<p>总上所述，第一次找直径L1，把边权变为-1<br>第二次找到直径L2，答案即$2(n-1)-(L1-1)-(L2-1)$</p>
<p>有木有觉得apio的图片非常良心</p>

</div></div></p>
<h3 id="9-CH-56C-异象石"><a href="#9-CH-56C-异象石" class="headerlink" title="9 CH#56C 异象石"></a>9 CH#56C 异象石</h3><p>8.30 难度2<br><div><div class="fold_hider"><div class="close hider_title">请先思考后再展开</div></div><div class="fold">
<p>先从每个节点上都有石头的情况开始考虑<br>如果从边的角度，那就是边总长<br>但因为这道题，主要从点的情况考虑，所以转化为，按照dfs搜索顺序，经过的相邻两点间距离/2<br>而对于不满的情况也是类似，把存在的所有点，按照dfs序收尾相接，相邻间距离和即为答案<br>那么具体实现的时候，可以搞一个set，用upper_bound等找相邻并动态维护当前总和即可</p>

</div></div></p>
<h3 id="10-BJWC2010-严格次小生成树"><a href="#10-BJWC2010-严格次小生成树" class="headerlink" title="10 BJWC2010 严格次小生成树"></a>10 BJWC2010 严格次小生成树</h3><p>8.30 难度2<br><div><div class="fold_hider"><div class="close hider_title">请先思考后再展开</div></div><div class="fold">
<p>按照惯例，对于这种在树上有非树边的问题，可以考虑一下，由非树边产生的环<br>例如本题，对于这个环，我们断掉任何一个，整个图依然是树（本来就是挂起来的无向无环图）<br>所以说，对于每条边，其贡献就是，把它替换掉原本树上路径中最大那一条产生的差<br>然后因为求的是严格次小，所以有种特殊情况，就是最大那个和当前边相同长</p>
<p>引理：<br>在最小生成树原本的路径中，一定不会有比当前非树边大的边</p>
<p>证明：<br>否则应该被当前非树边替换掉（替换掉一定不会有其他副作用之类，还是那句话，树本来就是挂起来的无向无环图）</p>
<p>那么也就是我们还需要且只需要再考虑次大值<br>具体实现的话，用一个倍增st表维护一下就好了（以倍增lca为框架）</p>

</div></div></p>
<h3 id="11-IOI2008-Island"><a href="#11-IOI2008-Island" class="headerlink" title="11 IOI2008 Island"></a>11 IOI2008 Island</h3><p>8.30 难度1<br><div><div class="fold_hider"><div class="close hider_title">请先思考后再展开</div></div><div class="fold">
<p>题意为，给出一个基环树森林，每个节点只能去一次，起点任意<br>跨基环树的时候，不能回到曾经去过的基环树<br>求最大化的【经过的基环树边的总和】<br>显然答案就是每个基环树内直径之和<br>然后基环树直径这种东西，写个dfs找环，dfs向下找最大深度，然后套个单调队列就好了</p>

</div></div></p>
<h3 id="12-6401-创世纪"><a href="#12-6401-创世纪" class="headerlink" title="12 6401 创世纪"></a>12 6401 创世纪</h3><p>8.30 难度2<br><div><div class="fold_hider"><div class="close hider_title">请先思考后再展开</div></div><div class="fold">
<p>在lxj的提醒下才想到正解……<br>其实一点都不难</p>
<p>图显然是一个内向树森林，要求选自己，则至少一个孩子不被选<br>考虑dp，$f(x,0/1)$表示当前子树满足条件时，x选择0/1的最大选择节点数<br>先搞定树上的部分，如果枚举固定一个孩子不选，然后其他乱搞，但给个菊花图就会炸<br>不难想到取补，把任意情况减去所有孩子都选了的情况（套路之记录次小值）</p>
<p>对于环上的怎么搞呢？<br>看一眼<a href="b119.html">这里</a>就知道了</p>

</div></div></p>
<h3 id="13-POI2008-BLO-Blockade"><a href="#13-POI2008-BLO-Blockade" class="headerlink" title="13 POI2008 BLO-Blockade"></a>13 POI2008 BLO-Blockade</h3><p>8.31 难度2<br><div><div class="fold_hider"><div class="close hider_title">请先思考后再展开</div></div><div class="fold">
<p><a href="293.html">教程</a><br>然后还是不会做……</p>
<p>在搜索树上考虑<br>对于每个节点，假如它不是割点，那么只有它和其他人是联通块，贡献为$2(n-1)$<br>而如果是割点，我们需要知道产生了多少个联通块，以及他们的大小</p>
<p>但怎么找？<br>$low_y \leq dfn_x$<br>这等价于割点的判定条件<br>主要考虑是可以相等，因为每次我们会断掉所有的边</p>
<p>联通块有三种：</p>
<ol>
<li>x自己，大小1</li>
<li>共有t个满足上面的条件，大小为在搜索树上的子树大小</li>
<li>剩下的所有点（假如大小不为0，则一定存在）</li>
</ol>
<p>第三点非常容易想漏，所以说建议多构造几组数据，当然对拍也是可以如果求稳的话</p>
<p>时间复杂度$O(n+m)$<br><figure class="highlight cpp"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div><div class="line">25</div><div class="line">26</div><div class="line">27</div><div class="line">28</div><div class="line">29</div><div class="line">30</div><div class="line">31</div><div class="line">32</div><div class="line">33</div><div class="line">34</div><div class="line">35</div><div class="line">36</div><div class="line">37</div><div class="line">38</div><div class="line">39</div><div class="line">40</div><div class="line">41</div><div class="line">42</div><div class="line">43</div><div class="line">44</div><div class="line">45</div><div class="line">46</div><div class="line">47</div><div class="line">48</div><div class="line">49</div><div class="line">50</div><div class="line">51</div><div class="line">52</div><div class="line">53</div><div class="line">54</div><div class="line">55</div><div class="line">56</div><div class="line">57</div><div class="line">58</div><div class="line">59</div><div class="line">60</div><div class="line">61</div><div class="line">62</div><div class="line">63</div><div class="line">64</div><div class="line">65</div><div class="line">66</div><div class="line">67</div><div class="line">68</div><div class="line">69</div><div class="line">70</div><div class="line">71</div><div class="line">72</div><div class="line">73</div><div class="line">74</div><div class="line">75</div><div class="line">76</div><div class="line">77</div><div class="line">78</div><div class="line">79</div><div class="line">80</div><div class="line">81</div><div class="line">82</div><div class="line">83</div></pre></td><td class="code"><pre><div class="line"><span class="comment">//Zory-2018</span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;cmath&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;cstdio&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;cstring&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;cstdlib&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;map&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;set&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;queue&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;deque&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;bitset&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;vector&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;algorithm&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;iostream&gt;</span></span></div><div class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</div><div class="line"></div><div class="line"><span class="keyword">namespace</span> mine</div><div class="line">&#123;</div><div class="line">    <span class="keyword">typedef</span> <span class="keyword">long</span> <span class="keyword">long</span> ll;</div><div class="line">    <span class="meta">#<span class="meta-keyword">define</span> double long double</span></div><div class="line">    <span class="keyword">const</span> <span class="keyword">int</span> MAX_N=<span class="number">110000</span>,MAX_M=<span class="number">510000</span>;</div><div class="line">    <span class="keyword">const</span> <span class="keyword">int</span> INF=<span class="number">0x3f3f3f3f</span>;</div><div class="line">    <span class="function"><span class="keyword">int</span> <span class="title">mymax</span><span class="params">(<span class="keyword">int</span> x,<span class="keyword">int</span> y)</span> </span>&#123;<span class="keyword">return</span> x&gt;y?x:y;&#125;</div><div class="line">    <span class="function"><span class="keyword">int</span> <span class="title">mymin</span><span class="params">(<span class="keyword">int</span> x,<span class="keyword">int</span> y)</span> </span>&#123;<span class="keyword">return</span> x&lt;y?x:y;&#125;</div><div class="line"></div><div class="line">    <span class="keyword">struct</span> Nod</div><div class="line">    &#123;</div><div class="line">        <span class="keyword">int</span> hou;</div><div class="line">        <span class="keyword">int</span> siz;</div><div class="line">        <span class="keyword">int</span> dfn,low;</div><div class="line">        ll ans;</div><div class="line">        Nod() &#123;hou=dfn=siz=<span class="number">0</span>;ans=<span class="number">0</span>;&#125;</div><div class="line">    &#125;p[MAX_N];</div><div class="line">    <span class="keyword">struct</span> Edge</div><div class="line">    &#123;</div><div class="line">        <span class="keyword">int</span> y,g;</div><div class="line">    &#125;e[MAX_M*<span class="number">2</span>];</div><div class="line">    <span class="keyword">int</span> ln=<span class="number">0</span>;</div><div class="line">    <span class="function"><span class="keyword">void</span> <span class="title">ins</span><span class="params">(<span class="keyword">int</span> x,<span class="keyword">int</span> y)</span> </span>&#123;e[++ln]=(Edge)&#123;y,p[x].hou&#125;;p[x].hou=ln;&#125;</div><div class="line">    <span class="function"><span class="keyword">int</span> <span class="title">oth</span><span class="params">(<span class="keyword">int</span> t)</span> </span>&#123;<span class="keyword">return</span> (t&amp;<span class="number">1</span>)?t+<span class="number">1</span>:t<span class="number">-1</span>;&#125;</div><div class="line">    <span class="keyword">int</span> id=<span class="number">0</span>;</div><div class="line"></div><div class="line">    <span class="keyword">int</span> n;</div><div class="line">    <span class="function"><span class="keyword">void</span> <span class="title">tarjan</span><span class="params">(<span class="keyword">int</span> x,<span class="keyword">int</span> from)</span></div><div class="line">    </span>&#123;</div><div class="line">        p[x].siz=<span class="number">1</span>;</div><div class="line">        p[x].dfn=p[x].low=++id;</div><div class="line"></div><div class="line">        <span class="keyword">int</span> sum=<span class="number">0</span>,cnt=<span class="number">0</span>;<span class="keyword">bool</span> cut=<span class="number">0</span>;</div><div class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> k=p[x].hou;k&gt;<span class="number">0</span>;k=e[k].g)</div><div class="line">        &#123;</div><div class="line">            <span class="keyword">int</span> y=e[k].y;</div><div class="line">            <span class="keyword">if</span>(p[y].dfn==<span class="number">0</span>)</div><div class="line">            &#123;</div><div class="line">                tarjan(y,k);</div><div class="line">                p[x].siz+=p[y].siz;</div><div class="line">                p[x].low=mymin(p[x].low,p[y].low);</div><div class="line"></div><div class="line">                <span class="keyword">if</span>(p[y].low&gt;=p[x].dfn)</div><div class="line">                &#123;</div><div class="line">                    cnt++;</div><div class="line">                    p[x].ans+=(ll)p[y].siz*(n-p[y].siz);</div><div class="line">                    sum+=p[y].siz;</div><div class="line">                    <span class="keyword">if</span>(x!=<span class="number">1</span> or cnt&gt;<span class="number">1</span>) cut=<span class="number">1</span>;</div><div class="line">                &#125;</div><div class="line">            &#125;</div><div class="line">            <span class="keyword">else</span> <span class="keyword">if</span>(k!=oth(from)) p[x].low=mymin(p[x].low,p[y].dfn);</div><div class="line">        &#125;</div><div class="line">        <span class="keyword">if</span>(cut) p[x].ans+=ll(n-sum<span class="number">-1</span>)*(sum+<span class="number">1</span>)+(n<span class="number">-1</span>);</div><div class="line">        <span class="keyword">else</span> p[x].ans=<span class="number">2</span>*(n<span class="number">-1</span>);<span class="comment">//注意要直接赋值</span></div><div class="line">    &#125;</div><div class="line">    <span class="function"><span class="keyword">void</span> <span class="title">main</span><span class="params">()</span></div><div class="line">    </span>&#123;</div><div class="line">        <span class="keyword">int</span> m;<span class="built_in">scanf</span>(<span class="string">"%d%d"</span>,&amp;n,&amp;m);</div><div class="line">        <span class="keyword">while</span>(m--) &#123;<span class="keyword">int</span> x,y;<span class="built_in">scanf</span>(<span class="string">"%d%d"</span>,&amp;x,&amp;y);ins(x,y);ins(y,x);&#125;<span class="comment">//无重边</span></div><div class="line">        tarjan(<span class="number">1</span>,<span class="number">-1</span>);</div><div class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=n;i++) <span class="built_in">printf</span>(<span class="string">"%lld\n"</span>,p[i].ans);</div><div class="line">    &#125;</div><div class="line">&#125;;</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></div><div class="line"></span>&#123;</div><div class="line">    mine::main();</div><div class="line">&#125;</div></pre></td></tr></table></figure></p>

</div></div></p>
<h3 id="14-poj3694-Network"><a href="#14-poj3694-Network" class="headerlink" title="14 poj3694 Network"></a>14 poj3694 Network</h3><p>8.31 难度1<br><div><div class="fold_hider"><div class="close hider_title">请先思考后再展开</div></div><div class="fold">
<p><a href="293.html">教程</a><br>考虑合并每个e-DCC，形成一棵树<br>然后倍增预处理一下lca</p>
<p>然后对于操作，其实就是合并x到y树上路径上的所有点，这个可以考虑用并查集维护<br>由于单个的小合并操作，只会发生n次，即使并查集log，也只有nlogn<br>而这个复杂度是超脱于询问这个循环之外的总复杂度</p>
<p>其实细节挺多的，大致流程：</p>
<ol>
<li>tarjan找到e-DCC，确定代表元素，初始化其并查集（最后别漏了根节点）</li>
<li>建立新的边目录，预处理倍增lca</li>
<li>回答询问的时候，一个个向上跳，维护割边数量cnt<figure class="highlight cpp"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div><div class="line">25</div><div class="line">26</div><div class="line">27</div><div class="line">28</div><div class="line">29</div><div class="line">30</div><div class="line">31</div><div class="line">32</div><div class="line">33</div><div class="line">34</div><div class="line">35</div><div class="line">36</div><div class="line">37</div><div class="line">38</div><div class="line">39</div><div class="line">40</div><div class="line">41</div><div class="line">42</div><div class="line">43</div><div class="line">44</div><div class="line">45</div><div class="line">46</div><div class="line">47</div><div class="line">48</div><div class="line">49</div><div class="line">50</div><div class="line">51</div><div class="line">52</div><div class="line">53</div><div class="line">54</div><div class="line">55</div><div class="line">56</div><div class="line">57</div><div class="line">58</div><div class="line">59</div><div class="line">60</div><div class="line">61</div><div class="line">62</div><div class="line">63</div><div class="line">64</div><div class="line">65</div><div class="line">66</div><div class="line">67</div><div class="line">68</div><div class="line">69</div><div class="line">70</div><div class="line">71</div><div class="line">72</div><div class="line">73</div><div class="line">74</div><div class="line">75</div><div class="line">76</div><div class="line">77</div><div class="line">78</div><div class="line">79</div><div class="line">80</div><div class="line">81</div><div class="line">82</div><div class="line">83</div><div class="line">84</div><div class="line">85</div><div class="line">86</div><div class="line">87</div><div class="line">88</div><div class="line">89</div><div class="line">90</div><div class="line">91</div><div class="line">92</div><div class="line">93</div><div class="line">94</div><div class="line">95</div><div class="line">96</div><div class="line">97</div><div class="line">98</div><div class="line">99</div><div class="line">100</div><div class="line">101</div><div class="line">102</div><div class="line">103</div><div class="line">104</div><div class="line">105</div><div class="line">106</div><div class="line">107</div><div class="line">108</div><div class="line">109</div><div class="line">110</div><div class="line">111</div><div class="line">112</div><div class="line">113</div><div class="line">114</div><div class="line">115</div><div class="line">116</div><div class="line">117</div><div class="line">118</div><div class="line">119</div><div class="line">120</div><div class="line">121</div><div class="line">122</div><div class="line">123</div><div class="line">124</div><div class="line">125</div><div class="line">126</div><div class="line">127</div><div class="line">128</div><div class="line">129</div><div class="line">130</div><div class="line">131</div><div class="line">132</div><div class="line">133</div><div class="line">134</div><div class="line">135</div><div class="line">136</div><div class="line">137</div><div class="line">138</div><div class="line">139</div><div class="line">140</div><div class="line">141</div><div class="line">142</div><div class="line">143</div><div class="line">144</div><div class="line">145</div><div class="line">146</div><div class="line">147</div><div class="line">148</div><div class="line">149</div><div class="line">150</div><div class="line">151</div><div class="line">152</div><div class="line">153</div><div class="line">154</div><div class="line">155</div><div class="line">156</div><div class="line">157</div></pre></td><td class="code"><pre><div class="line"><span class="comment">//Zory-2018</span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;cmath&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;cstdio&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;cstring&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;cstdlib&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;map&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;set&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;queue&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;deque&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;bitset&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;vector&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;algorithm&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;iostream&gt;</span></span></div><div class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</div><div class="line"></div><div class="line"><span class="keyword">namespace</span> mine</div><div class="line">&#123;</div><div class="line">    <span class="keyword">typedef</span> <span class="keyword">long</span> <span class="keyword">long</span> ll;</div><div class="line">    <span class="meta">#<span class="meta-keyword">define</span> double long double</span></div><div class="line">    <span class="keyword">const</span> <span class="keyword">int</span> MAX_N=<span class="number">110000</span>,MAX_M=<span class="number">410000</span>;</div><div class="line">    <span class="keyword">const</span> <span class="keyword">int</span> INF=<span class="number">0x3f3f3f3f</span>;</div><div class="line">    <span class="function"><span class="keyword">int</span> <span class="title">mymax</span><span class="params">(<span class="keyword">int</span> x,<span class="keyword">int</span> y)</span> </span>&#123;<span class="keyword">return</span> x&gt;y?x:y;&#125;</div><div class="line">    <span class="function"><span class="keyword">int</span> <span class="title">mymin</span><span class="params">(<span class="keyword">int</span> x,<span class="keyword">int</span> y)</span> </span>&#123;<span class="keyword">return</span> x&lt;y?x:y;&#125;</div><div class="line"></div><div class="line">    <span class="keyword">struct</span> Nod</div><div class="line">    &#123;</div><div class="line">        <span class="keyword">int</span> hou;</div><div class="line">        <span class="keyword">int</span> dfn,low;</div><div class="line">        <span class="keyword">int</span> fa;<span class="comment">//块父亲</span></div><div class="line">    &#125;p[MAX_N];</div><div class="line">    <span class="keyword">struct</span> Edge</div><div class="line">    &#123;</div><div class="line">        <span class="keyword">int</span> x,y,g;</div><div class="line">    &#125;e[MAX_M*<span class="number">2</span>];</div><div class="line">    <span class="keyword">int</span> ln;</div><div class="line">    <span class="function"><span class="keyword">void</span> <span class="title">ins</span><span class="params">(<span class="keyword">int</span> x,<span class="keyword">int</span> y)</span></div><div class="line">    </span>&#123;</div><div class="line">        ln++;</div><div class="line">        e[ln].x=x;e[ln].y=y;</div><div class="line">        e[ln].g=p[x].hou;</div><div class="line">        p[x].hou=ln;</div><div class="line">    &#125;</div><div class="line">    <span class="function"><span class="keyword">int</span> <span class="title">oth</span><span class="params">(<span class="keyword">int</span> t)</span> </span>&#123;<span class="keyword">return</span> (t&amp;<span class="number">1</span>)?(t+<span class="number">1</span>):(t<span class="number">-1</span>);&#125;</div><div class="line"></div><div class="line">    <span class="keyword">int</span> id[MAX_N];<span class="comment">//并查集维护，所在的块</span></div><div class="line">    <span class="function"><span class="keyword">int</span> <span class="title">findfa</span><span class="params">(<span class="keyword">int</span> x)</span> </span>&#123;<span class="keyword">return</span> id[x]=(x==id[x]?x:findfa(id[x]));&#125;</div><div class="line"></div><div class="line">    <span class="function"><span class="keyword">void</span> <span class="title">dfs</span><span class="params">(<span class="keyword">int</span> x,<span class="keyword">int</span> fa,<span class="keyword">int</span> now)</span></div><div class="line">    </span>&#123;</div><div class="line">        id[x]=now;</div><div class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> k=p[x].hou;k&gt;<span class="number">0</span>;k=e[k].g) <span class="keyword">if</span>(e[k].y!=fa and id[e[k].y]==<span class="number">0</span>) dfs(e[k].y,x,now);</div><div class="line">    &#125;</div><div class="line"></div><div class="line">    <span class="keyword">int</span> ct,cnt;</div><div class="line">    <span class="function"><span class="keyword">void</span> <span class="title">tarjan</span><span class="params">(<span class="keyword">int</span> x,<span class="keyword">int</span> from)</span></div><div class="line">    </span>&#123;</div><div class="line">        p[x].dfn=p[x].low=++ct;</div><div class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> k=p[x].hou;k&gt;<span class="number">0</span>;k=e[k].g)</div><div class="line">        &#123;</div><div class="line">            <span class="keyword">int</span> y=e[k].y;</div><div class="line">            <span class="keyword">if</span>(p[y].dfn==<span class="number">0</span>)</div><div class="line">            &#123;</div><div class="line">                tarjan(y,k);</div><div class="line">                p[x].low=mymin(p[x].low,p[y].low);</div><div class="line">                <span class="keyword">if</span>(p[y].low&gt;p[x].dfn)<span class="comment">//割边</span></div><div class="line">                &#123;</div><div class="line">                    cnt++;<span class="comment">//割边数</span></div><div class="line">                    p[y].fa=x;</div><div class="line">                    dfs(y,x,y);</div><div class="line">                &#125;</div><div class="line">            &#125;</div><div class="line">            <span class="keyword">else</span> <span class="keyword">if</span>(k!=oth(from)) p[x].low=mymin(p[x].low,p[y].dfn);</div><div class="line">        &#125;</div><div class="line">    &#125;</div><div class="line"></div><div class="line">    <span class="keyword">int</span> hou[MAX_N],dep[MAX_N];</div><div class="line">    Edge e2[MAX_M*<span class="number">2</span>];</div><div class="line">    <span class="keyword">int</span> ln2;</div><div class="line">    <span class="function"><span class="keyword">void</span> <span class="title">ins2</span><span class="params">(<span class="keyword">int</span> x,<span class="keyword">int</span> y)</span></div><div class="line">    </span>&#123;</div><div class="line">        ln2++;</div><div class="line">        e2[ln2].y=y;e2[ln2].g=hou[x];</div><div class="line">        hou[x]=ln2;</div><div class="line">    &#125;</div><div class="line"></div><div class="line">    <span class="keyword">int</span> f[MAX_N][<span class="number">20</span>];</div><div class="line">    <span class="function"><span class="keyword">void</span> <span class="title">pre</span><span class="params">(<span class="keyword">int</span> x,<span class="keyword">int</span> fa)</span></div><div class="line">    </span>&#123;</div><div class="line">        dep[x]=dep[fa]+<span class="number">1</span>;</div><div class="line">        f[x][<span class="number">0</span>]=fa;<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;<span class="number">20</span>;i++) f[x][i]=f[f[x][i<span class="number">-1</span>]][i<span class="number">-1</span>];</div><div class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> k=hou[x];k&gt;<span class="number">0</span>;k=e2[k].g)</div><div class="line">        &#123;</div><div class="line">            <span class="keyword">int</span> y=e2[k].y;<span class="keyword">if</span>(y==fa) <span class="keyword">continue</span>;</div><div class="line">            pre(y,x);</div><div class="line">        &#125;</div><div class="line">    &#125;</div><div class="line">    <span class="keyword">int</span> n,m;</div><div class="line">    <span class="function"><span class="keyword">void</span> <span class="title">make_graph</span><span class="params">()</span></div><div class="line">    </span>&#123;</div><div class="line">        ln=<span class="number">0</span>;<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=n;i++) p[i].hou=p[i].dfn=<span class="number">0</span>;</div><div class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=m;i++)</div><div class="line">        &#123;</div><div class="line">            <span class="keyword">int</span> x,y;<span class="built_in">scanf</span>(<span class="string">"%d%d"</span>,&amp;x,&amp;y);</div><div class="line">            ins(x,y);ins(y,x);<span class="comment">//无自环</span></div><div class="line">        &#125;</div><div class="line"></div><div class="line">        cnt=<span class="number">0</span>;ct=<span class="number">0</span>;<span class="built_in">memset</span>(id,<span class="number">0</span>,<span class="keyword">sizeof</span> id);</div><div class="line">        tarjan(<span class="number">1</span>,<span class="number">-1</span>);dfs(<span class="number">1</span>,<span class="number">0</span>,<span class="number">1</span>);</div><div class="line"></div><div class="line">        ln2=<span class="number">0</span>;<span class="built_in">memset</span>(hou,<span class="number">0</span>,<span class="keyword">sizeof</span> hou);</div><div class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=<span class="number">2</span>*m;i+=<span class="number">2</span>)</div><div class="line">        &#123;</div><div class="line">            <span class="keyword">int</span> fx=findfa(e[i].x),fy=findfa(e[i].y);</div><div class="line">            <span class="keyword">if</span>(fx!=fy) ins2(fx,fy),ins2(fy,fx);</div><div class="line">        &#125;</div><div class="line">        pre(<span class="number">1</span>,<span class="number">0</span>);</div><div class="line">    &#125;</div><div class="line">    <span class="keyword">int</span> bin[<span class="number">20</span>];</div><div class="line">    <span class="function"><span class="keyword">int</span> <span class="title">getlca</span><span class="params">(<span class="keyword">int</span> x,<span class="keyword">int</span> y)</span></div><div class="line">    </span>&#123;</div><div class="line">        <span class="keyword">if</span>(dep[x]&lt;dep[y]) swap(x,y);</div><div class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">19</span>;i&gt;=<span class="number">0</span>;i--) <span class="keyword">if</span>(dep[x]-dep[y]&gt;=bin[i]) x=f[x][i];</div><div class="line">        <span class="keyword">if</span>(x==y) <span class="keyword">return</span> x;</div><div class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">19</span>;i&gt;=<span class="number">0</span>;i--) <span class="keyword">if</span>(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];</div><div class="line">        <span class="keyword">return</span> f[x][<span class="number">0</span>];</div><div class="line">    &#125;</div><div class="line"></div><div class="line">    <span class="function"><span class="keyword">int</span> <span class="title">solve</span><span class="params">()</span></div><div class="line">    </span>&#123;</div><div class="line">        <span class="keyword">int</span> x,y;<span class="built_in">scanf</span>(<span class="string">"%d%d"</span>,&amp;x,&amp;y);</div><div class="line">        <span class="keyword">int</span> fx=findfa(x),fy=findfa(y),lca=findfa(getlca(fx,fy));<span class="comment">//debug getlca(x,y)</span></div><div class="line">        <span class="keyword">while</span>(fx!=lca) cnt--,id[fx]=lca,fx=findfa(p[fx].fa);</div><div class="line">        <span class="keyword">while</span>(fy!=lca) cnt--,id[fy]=lca,fy=findfa(p[fy].fa);</div><div class="line">        <span class="comment">//因为每次findfa找最上面的代表元素，所以p[fx].fa一定是另一个节点</span></div><div class="line">        <span class="keyword">return</span> cnt;</div><div class="line">    &#125;</div><div class="line">    <span class="function"><span class="keyword">void</span> <span class="title">main</span><span class="params">()</span></div><div class="line">    </span>&#123;</div><div class="line">        bin[<span class="number">0</span>]=<span class="number">1</span>;<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;<span class="number">20</span>;i++) bin[i]=bin[i<span class="number">-1</span>]&lt;&lt;<span class="number">1</span>;</div><div class="line"></div><div class="line">        <span class="keyword">int</span> cas=<span class="number">0</span>;</div><div class="line">        <span class="keyword">while</span>(<span class="number">1</span>)</div><div class="line">        &#123;</div><div class="line">            <span class="built_in">scanf</span>(<span class="string">"%d%d"</span>,&amp;n,&amp;m);</div><div class="line">            <span class="keyword">if</span>(n==<span class="number">0</span>) <span class="keyword">break</span>;</div><div class="line">            <span class="built_in">printf</span>(<span class="string">"Case %d:\n"</span>,++cas);</div><div class="line">            make_graph();</div><div class="line">            <span class="keyword">int</span> q;<span class="built_in">scanf</span>(<span class="string">"%d"</span>,&amp;q);</div><div class="line">            <span class="keyword">while</span>(q--) <span class="built_in">printf</span>(<span class="string">"%d\n"</span>,solve());</div><div class="line">        &#125;</div><div class="line">    &#125;</div><div class="line">&#125;;</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></div><div class="line"></span>&#123;</div><div class="line">    mine::main();</div><div class="line">&#125;</div></pre></td></tr></table></figure>
</li>
</ol>

</div></div></p>
<h3 id="15-poj2942-Knights-of-the-Round-Table"><a href="#15-poj2942-Knights-of-the-Round-Table" class="headerlink" title="15 poj2942 Knights of the Round Table"></a>15 poj2942 Knights of the Round Table</h3><p>9.1 难度2<br><div><div class="fold_hider"><div class="close hider_title">请先思考后再展开</div></div><div class="fold">
<p>题意：找出有多少个骑士，无法出席任何会议<br>会议的要求是有奇数个人，成环形后相邻的人没有憎恨关系</p>
<p>因为是环形，考虑连成一个环，不难想到建立一个补图，用【无憎恨关系】来建边<br>那么就转化成，有多少个点，不在任何奇环（奇数个点的简单环）中</p>
<p>然后判断奇环可以染色，但怎么标记呢？暴力搞我自己都能出个数据卡成nm<br>百思不得其姐，又去膜题解<br>题解给出的又是两个结论……还好这一次，这两个结论的证明都很简单</p>
<p>结论1：奇环不会垮v-DCC存在<br>证明：显然两个v-DCC能合并成一个v-DCC，与v-DCC的“极大”矛盾</p>
<p>结论2：如果某个v-DCC中有奇环，则整个v-DCC的每个节点，至少被一个奇环所包含<br>假设有奇环外节点x，总是能和奇环上任意两个节点vi和vj形成奇环，<br>因为无论【x到vi+x到vj】的奇偶性如何，奇环上两个点间距离总是能取奇数或者偶数……<br>因为奇=奇+偶，亘古不变……</p>
<p>怎么说呢？这两个结论都不是太好猜，但偏偏缺一不可</p>

</div></div></p>
<h3 id="16-poj1236-Network-of-Schools"><a href="#16-poj1236-Network-of-Schools" class="headerlink" title="16 poj1236 Network of Schools"></a>16 poj1236 Network of Schools</h3><p>9.1 难度2<br><div><div class="fold_hider"><div class="close hider_title">请先思考后再展开</div></div><div class="fold">
<p>开始想法：<br>设强连通分量缩点后，a=【入度=0】，b=【出度=0】<br>那么第一问求a，第二问求b</p>
<p>其实已经和正解接近了，但还是错误的<br>第二问求的其实是max(a,b)<br>重新思考，<br>对于入度为0的scc，如果起点不在这里就凉了，要消除掉<br>对于出度为0的scc，如果起点在这里就凉了，要消除掉<br>因为一次可以同时消除两种各一个，得证</p>

</div></div></p>
<h3 id="17-poj2226-Muddy-Fields"><a href="#17-poj2226-Muddy-Fields" class="headerlink" title="17 poj2226 Muddy Fields"></a>17 poj2226 Muddy Fields</h3><p>9.7 难度2<br><div><div class="fold_hider"><div class="close hider_title">请先思考后再展开</div></div><div class="fold">
<p>不会做的经典模型<br>将连续的泥地分为行泥泞块和列泥泞块，形成了二分图<br>那么，对于每个小泥地，至少要被其中一种覆盖<br>那么把每个小泥地作为边，恰好连接两个元<br>求最小覆盖即可</p>

</div></div></p>
<h3 id="18-6902-Vani和Cl2捉迷藏"><a href="#18-6902-Vani和Cl2捉迷藏" class="headerlink" title="18 6902 Vani和Cl2捉迷藏"></a>18 6902 Vani和Cl2捉迷藏</h3><p>9.9 难度2<br><div><div class="fold_hider"><div class="close hider_title">请先思考后再展开</div></div><div class="fold">
<p>神仙结论题，结论不好猜，证明不好想，但出得挺好<br>因为不能有路径相连，可以联想到传递闭包（居然没有想到），转移为边的相连（构造新图，边就是用闭包得出来的结果）<br>那么现在类似于要找最大独立集</p>
<p>结论：总能在【最小可重复点覆盖路径】的每条路径中，找出一个点<br>证明：<br>首先，【隐藏点】显然小于等于【路径数量】<br>那么我们只要说我们能构造出一种方法来，就相当于证明了结论（这也是一种有趣的证明方法）</p>
<p>先取出每个路径的终点，作为集合A，将A走一步能到达的节点作为next(A)<br>按照题意，$A \cap next(A)=\varnothing$ ，所以我们要有所调整<br>取出这种元素，然后在其所属的【最小可重复点覆盖路径】上，往起点方向跳，<br>一定能找到一个元素不属于next(A)，否则意味着整条路径都是可以被别人覆盖掉的，违反了我们先前最小的定义<br>找到后，取代原先的元素，如此重复下去，最后总是能满足条件的<br>综上所述，存在一种方案，满足条件<br><figure class="highlight cpp"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div><div class="line">25</div><div class="line">26</div><div class="line">27</div><div class="line">28</div><div class="line">29</div><div class="line">30</div><div class="line">31</div><div class="line">32</div><div class="line">33</div><div class="line">34</div><div class="line">35</div><div class="line">36</div><div class="line">37</div><div class="line">38</div><div class="line">39</div><div class="line">40</div><div class="line">41</div><div class="line">42</div><div class="line">43</div><div class="line">44</div><div class="line">45</div><div class="line">46</div><div class="line">47</div><div class="line">48</div><div class="line">49</div><div class="line">50</div><div class="line">51</div><div class="line">52</div><div class="line">53</div><div class="line">54</div><div class="line">55</div><div class="line">56</div><div class="line">57</div><div class="line">58</div><div class="line">59</div><div class="line">60</div><div class="line">61</div><div class="line">62</div><div class="line">63</div><div class="line">64</div><div class="line">65</div><div class="line">66</div><div class="line">67</div><div class="line">68</div><div class="line">69</div><div class="line">70</div><div class="line">71</div><div class="line">72</div><div class="line">73</div><div class="line">74</div><div class="line">75</div><div class="line">76</div><div class="line">77</div><div class="line">78</div><div class="line">79</div><div class="line">80</div><div class="line">81</div><div class="line">82</div><div class="line">83</div><div class="line">84</div><div class="line">85</div><div class="line">86</div></pre></td><td class="code"><pre><div class="line"><span class="comment">//Zory-2018</span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;cmath&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;cstdio&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;cstring&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;cstdlib&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;map&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;set&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;queue&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;deque&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;bitset&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;vector&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;algorithm&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;iostream&gt;</span></span></div><div class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</div><div class="line"></div><div class="line"><span class="keyword">namespace</span> mine</div><div class="line">&#123;</div><div class="line">	<span class="keyword">typedef</span> <span class="keyword">long</span> <span class="keyword">long</span> ll;</div><div class="line">	<span class="keyword">const</span> <span class="keyword">int</span> MAX_N=<span class="number">210</span>;</div><div class="line"></div><div class="line">	<span class="keyword">int</span> n,m;</div><div class="line">	<span class="keyword">int</span> match1[MAX_N],match2[MAX_N];</div><div class="line">	<span class="keyword">int</span> ask[MAX_N],ti;<span class="comment">//时间戳</span></div><div class="line">	<span class="keyword">bool</span> mp[MAX_N][MAX_N];</div><div class="line">	<span class="function"><span class="keyword">bool</span> <span class="title">fd</span><span class="params">(<span class="keyword">int</span> x)</span></div><div class="line">	</span>&#123;</div><div class="line">		<span class="keyword">for</span>(<span class="keyword">int</span> y=<span class="number">1</span>;y&lt;=n;y++)</div><div class="line">		&#123;</div><div class="line">			<span class="keyword">if</span>(!mp[x][y] or ask[y]==ti) <span class="keyword">continue</span>;</div><div class="line">			ask[y]=ti;</div><div class="line"></div><div class="line">			<span class="keyword">if</span>(match2[y]==<span class="number">0</span> or fd(match2[y]))</div><div class="line">			&#123;</div><div class="line">				match1[x]=y;</div><div class="line">				match2[y]=x;</div><div class="line">				<span class="keyword">return</span> <span class="number">1</span>;</div><div class="line">			&#125;</div><div class="line">		&#125;</div><div class="line">		<span class="keyword">return</span> <span class="number">0</span>;</div><div class="line">	&#125;</div><div class="line"></div><div class="line">	<span class="keyword">bool</span> A[MAX_N],Anx[MAX_N];</div><div class="line">	<span class="function"><span class="keyword">int</span> <span class="title">up</span><span class="params">(<span class="keyword">int</span> x)</span> </span>&#123;<span class="keyword">return</span> match2[x];&#125;</div><div class="line">	<span class="function"><span class="keyword">void</span> <span class="title">main</span><span class="params">()</span></div><div class="line">	</span>&#123;</div><div class="line">		<span class="built_in">scanf</span>(<span class="string">"%d%d"</span>,&amp;n,&amp;m);</div><div class="line">		<span class="keyword">while</span>(m--)</div><div class="line">		&#123;</div><div class="line">			<span class="keyword">int</span> x,y;<span class="built_in">scanf</span>(<span class="string">"%d%d"</span>,&amp;x,&amp;y);</div><div class="line">			mp[x][y]=<span class="number">1</span>;</div><div class="line">		&#125;</div><div class="line">		<span class="comment">//传递闭包</span></div><div class="line">		<span class="keyword">for</span>(<span class="keyword">int</span> k=<span class="number">1</span>;k&lt;=n;k++)</div><div class="line">			<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=n;i++)</div><div class="line">				<span class="keyword">for</span>(<span class="keyword">int</span> j=<span class="number">1</span>;j&lt;=n;j++)</div><div class="line">					mp[i][j]|=mp[i][k]&amp;mp[k][j];</div><div class="line"></div><div class="line">		<span class="comment">//二分图匹配</span></div><div class="line">		<span class="keyword">int</span> ans=<span class="number">0</span>;<span class="keyword">for</span>(ti=<span class="number">1</span>;ti&lt;=n;ti++) ans+=fd(ti);</div><div class="line">		<span class="built_in">printf</span>(<span class="string">"%d\n"</span>,n-ans);</div><div class="line"></div><div class="line">		<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=n;i++) <span class="keyword">if</span>(match1[i]==<span class="number">0</span>) A[i]=<span class="number">1</span>;</div><div class="line">		<span class="keyword">bool</span> modif=<span class="number">1</span>;</div><div class="line">		<span class="keyword">while</span>(modif)</div><div class="line">		&#123;</div><div class="line">			modif=<span class="number">0</span>;</div><div class="line"></div><div class="line">			<span class="built_in">memset</span>(Anx,<span class="number">0</span>,<span class="keyword">sizeof</span> Anx);</div><div class="line">			<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=n;i++) <span class="keyword">if</span>(A[i])</div><div class="line">				<span class="keyword">for</span>(<span class="keyword">int</span> j=<span class="number">1</span>;j&lt;=n;j++) <span class="keyword">if</span>(mp[i][j]) Anx[j]=<span class="number">1</span>;</div><div class="line">			<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=n;i++) <span class="keyword">if</span>(A[i] and Anx[i])</div><div class="line">				&#123;</div><div class="line">					modif=<span class="number">1</span>;</div><div class="line">					<span class="keyword">int</span> t=up(i);<span class="keyword">while</span>(Anx[t]) t=up(t);</div><div class="line">					A[i]=<span class="number">0</span>;A[t]=<span class="number">1</span>;</div><div class="line">					<span class="keyword">break</span>;</div><div class="line">				&#125;</div><div class="line">		&#125;</div><div class="line">		<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=n;i++) <span class="keyword">if</span>(A[i]) <span class="built_in">printf</span>(<span class="string">"%d "</span>,i);</div><div class="line">	&#125;</div><div class="line">&#125;;</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></div><div class="line"></span>&#123;</div><div class="line">	mine::main();</div><div class="line">&#125;</div></pre></td></tr></table></figure></p>

</div></div></p>
<h3 id="19-CH-17-舞动的夜晚"><a href="#19-CH-17-舞动的夜晚" class="headerlink" title="19 CH#17 舞动的夜晚"></a>19 CH#17 舞动的夜晚</h3><p>9.10 难度2<br><div><div class="fold_hider"><div class="close hider_title">请先思考后再展开</div></div><div class="fold">
<p>详见oi之路的二分图一章<br><figure class="highlight cpp"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div><div class="line">25</div><div class="line">26</div><div class="line">27</div><div class="line">28</div><div class="line">29</div><div class="line">30</div><div class="line">31</div><div class="line">32</div><div class="line">33</div><div class="line">34</div><div class="line">35</div><div class="line">36</div><div class="line">37</div><div class="line">38</div><div class="line">39</div><div class="line">40</div><div class="line">41</div><div class="line">42</div><div class="line">43</div><div class="line">44</div><div class="line">45</div><div class="line">46</div><div class="line">47</div><div class="line">48</div><div class="line">49</div><div class="line">50</div><div class="line">51</div><div class="line">52</div><div class="line">53</div><div class="line">54</div><div class="line">55</div><div class="line">56</div><div class="line">57</div><div class="line">58</div><div class="line">59</div><div class="line">60</div><div class="line">61</div><div class="line">62</div><div class="line">63</div><div class="line">64</div><div class="line">65</div><div class="line">66</div><div class="line">67</div><div class="line">68</div><div class="line">69</div><div class="line">70</div><div class="line">71</div><div class="line">72</div><div class="line">73</div><div class="line">74</div><div class="line">75</div><div class="line">76</div><div class="line">77</div><div class="line">78</div><div class="line">79</div><div class="line">80</div><div class="line">81</div><div class="line">82</div><div class="line">83</div><div class="line">84</div><div class="line">85</div><div class="line">86</div><div class="line">87</div><div class="line">88</div><div class="line">89</div><div class="line">90</div><div class="line">91</div><div class="line">92</div><div class="line">93</div><div class="line">94</div><div class="line">95</div><div class="line">96</div><div class="line">97</div><div class="line">98</div><div class="line">99</div><div class="line">100</div><div class="line">101</div><div class="line">102</div><div class="line">103</div><div class="line">104</div><div class="line">105</div><div class="line">106</div><div class="line">107</div><div class="line">108</div><div class="line">109</div><div class="line">110</div><div class="line">111</div><div class="line">112</div><div class="line">113</div><div class="line">114</div><div class="line">115</div><div class="line">116</div><div class="line">117</div><div class="line">118</div><div class="line">119</div><div class="line">120</div><div class="line">121</div><div class="line">122</div><div class="line">123</div><div class="line">124</div><div class="line">125</div><div class="line">126</div><div class="line">127</div><div class="line">128</div><div class="line">129</div><div class="line">130</div><div class="line">131</div><div class="line">132</div><div class="line">133</div><div class="line">134</div><div class="line">135</div></pre></td><td class="code"><pre><div class="line"><span class="comment">//Zory-2018</span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;cmath&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;cstdio&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;cstring&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;cstdlib&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;map&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;set&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;queue&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;deque&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;bitset&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;vector&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;algorithm&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;iostream&gt;</span></span></div><div class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</div><div class="line"></div><div class="line"><span class="keyword">namespace</span> mine</div><div class="line">&#123;</div><div class="line">	<span class="keyword">const</span> <span class="keyword">int</span> MAX_N=<span class="number">11000</span>,MAX_M=<span class="number">110000</span>;</div><div class="line">	<span class="function"><span class="keyword">int</span> <span class="title">mymin</span><span class="params">(<span class="keyword">int</span> x,<span class="keyword">int</span> y)</span> </span>&#123;<span class="keyword">return</span> x&lt;y?x:y;&#125;</div><div class="line"></div><div class="line">	<span class="keyword">struct</span> Nod</div><div class="line">	&#123;</div><div class="line">		<span class="keyword">int</span> hou;</div><div class="line">		<span class="keyword">bool</span> v;</div><div class="line">		Nod() &#123;hou=<span class="number">0</span>;v=<span class="number">0</span>;&#125;</div><div class="line">	&#125;p[MAX_N*<span class="number">2</span>];</div><div class="line">	<span class="keyword">struct</span> Edge</div><div class="line">	&#123;</div><div class="line">		<span class="keyword">int</span> y,g,c;</div><div class="line">	&#125;e[(MAX_N*<span class="number">2</span>+MAX_M)*<span class="number">2</span>];</div><div class="line">	<span class="function"><span class="keyword">int</span> <span class="title">oth</span><span class="params">(<span class="keyword">int</span> x)</span> </span>&#123;<span class="keyword">return</span> x&amp;<span class="number">1</span>?x+<span class="number">1</span>:x<span class="number">-1</span>;&#125;</div><div class="line">	<span class="keyword">int</span> ln=<span class="number">0</span>;</div><div class="line">	<span class="function"><span class="keyword">void</span> <span class="title">ins</span><span class="params">(<span class="keyword">int</span> x,<span class="keyword">int</span> y,<span class="keyword">int</span> c)</span></div><div class="line">	</span>&#123;</div><div class="line">		e[++ln]=(Edge)&#123;y,p[x].hou,c&#125;;p[x].hou=ln;</div><div class="line">		e[++ln]=(Edge)&#123;x,p[y].hou,<span class="number">0</span>&#125;;p[y].hou=ln;</div><div class="line">	&#125;</div><div class="line"></div><div class="line">	<span class="keyword">int</span> st,ed;</div><div class="line">	<span class="keyword">int</span> h[MAX_N*<span class="number">2</span>];</div><div class="line">	<span class="built_in">queue</span>&lt;<span class="keyword">int</span>&gt; q;</div><div class="line">	<span class="function"><span class="keyword">bool</span> <span class="title">bfs</span><span class="params">()</span></div><div class="line">	</span>&#123;</div><div class="line">		<span class="built_in">memset</span>(h,<span class="number">0</span>,<span class="keyword">sizeof</span> h);</div><div class="line">		q.push(st);h[st]=<span class="number">1</span>;</div><div class="line"></div><div class="line">		<span class="keyword">while</span>(!q.empty())</div><div class="line">		&#123;</div><div class="line">			<span class="keyword">int</span> x=q.front();q.pop();</div><div class="line">			<span class="keyword">for</span>(<span class="keyword">int</span> k=p[x].hou;k&gt;<span class="number">0</span>;k=e[k].g)</div><div class="line">			&#123;</div><div class="line">				<span class="keyword">int</span> y=e[k].y;</div><div class="line">				<span class="keyword">if</span>(h[y]==<span class="number">0</span> and e[k].c&gt;<span class="number">0</span>)</div><div class="line">				&#123;</div><div class="line">					h[y]=h[x]+<span class="number">1</span>;</div><div class="line">					q.push(y);</div><div class="line">				&#125;</div><div class="line">			&#125;</div><div class="line">		&#125;</div><div class="line">		<span class="keyword">return</span> h[ed]&gt;<span class="number">0</span>;</div><div class="line">	&#125;</div><div class="line">	<span class="function"><span class="keyword">int</span> <span class="title">dfs</span><span class="params">(<span class="keyword">int</span> x,<span class="keyword">int</span> flow)</span></div><div class="line">	</span>&#123;</div><div class="line">		<span class="keyword">if</span>(x==ed) <span class="keyword">return</span> flow;</div><div class="line">		<span class="keyword">int</span> out=<span class="number">0</span>;</div><div class="line">		<span class="keyword">for</span>(<span class="keyword">int</span> k=p[x].hou;k&gt;<span class="number">0</span>;k=e[k].g)</div><div class="line">		&#123;</div><div class="line">			<span class="keyword">int</span> y=e[k].y,fine=mymin(flow-out,e[k].c);</div><div class="line">			<span class="keyword">if</span>(h[y]==h[x]+<span class="number">1</span> and fine&gt;<span class="number">0</span>)<span class="comment">//注意e[k].c，可能改变了</span></div><div class="line">			&#123;</div><div class="line">				<span class="keyword">int</span> t=dfs(y,fine);</div><div class="line">				out+=t;e[k].c-=t;e[oth(k)].c+=t;</div><div class="line">			&#125;</div><div class="line">		&#125;</div><div class="line">		<span class="keyword">if</span>(out==<span class="number">0</span>) h[x]=<span class="number">0</span>;<span class="comment">//剪枝</span></div><div class="line">		<span class="keyword">return</span> out;</div><div class="line">	&#125;</div><div class="line"></div><div class="line">	<span class="keyword">int</span> dfn[MAX_N*<span class="number">2</span>],low[MAX_N*<span class="number">2</span>],id=<span class="number">0</span>;</div><div class="line">	<span class="keyword">int</span> sta[MAX_N*<span class="number">2</span>],top=<span class="number">0</span>;</div><div class="line">	<span class="keyword">bool</span> insta[MAX_N*<span class="number">2</span>];</div><div class="line">	<span class="keyword">int</span> belg[MAX_N*<span class="number">2</span>],cnt=<span class="number">0</span>;</div><div class="line">	<span class="function"><span class="keyword">void</span> <span class="title">tarjan</span><span class="params">(<span class="keyword">int</span> x)</span></div><div class="line">	</span>&#123;</div><div class="line">		dfn[x]=low[x]=++id;</div><div class="line">		sta[++top]=x;insta[x]=<span class="number">1</span>;</div><div class="line">		<span class="keyword">for</span>(<span class="keyword">int</span> k=p[x].hou;k&gt;<span class="number">0</span>;k=e[k].g)</div><div class="line">		&#123;</div><div class="line">			<span class="keyword">int</span> y=e[k].y;<span class="keyword">if</span>(e[k].c==<span class="number">0</span>) <span class="keyword">continue</span>;</div><div class="line">			<span class="keyword">if</span>(dfn[y]==<span class="number">0</span>) tarjan(y),low[x]=mymin(low[x],low[y]);</div><div class="line">			<span class="keyword">else</span> <span class="keyword">if</span>(insta[y]) low[x]=mymin(low[x],dfn[y]);</div><div class="line">		&#125;</div><div class="line">		<span class="keyword">if</span>(dfn[x]==low[x])</div><div class="line">		&#123;</div><div class="line">			++cnt;</div><div class="line">			<span class="keyword">int</span> now;</div><div class="line">			<span class="keyword">do</span></div><div class="line">			&#123;</div><div class="line">				now=sta[top--];</div><div class="line">				belg[now]=cnt;</div><div class="line">				insta[now]=<span class="number">0</span>;</div><div class="line">			&#125;<span class="keyword">while</span>(now!=x);</div><div class="line">		&#125;</div><div class="line">	&#125;</div><div class="line"></div><div class="line">	<span class="keyword">int</span> xx[MAX_M],yy[MAX_M];</div><div class="line">	<span class="function"><span class="keyword">void</span> <span class="title">main</span><span class="params">()</span></div><div class="line">	</span>&#123;</div><div class="line">		<span class="keyword">int</span> n,m,ct;<span class="built_in">scanf</span>(<span class="string">"%d%d%d"</span>,&amp;n,&amp;m,&amp;ct);</div><div class="line">		st=<span class="number">0</span>,ed=n+m+<span class="number">1</span>;</div><div class="line">		<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=n;i++) ins(st,i,<span class="number">1</span>);</div><div class="line">		<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=m;i++) ins(n+i,ed,<span class="number">1</span>);</div><div class="line">		<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=ct;i++)</div><div class="line">		&#123;</div><div class="line">			<span class="built_in">scanf</span>(<span class="string">"%d%d"</span>,&amp;xx[i],&amp;yy[i]);</div><div class="line">			ins(xx[i],n+yy[i],<span class="number">1</span>);</div><div class="line">		&#125;</div><div class="line"></div><div class="line">		<span class="keyword">while</span>(bfs()) dfs(st,<span class="number">0x3f3f3f3f</span>);</div><div class="line">		<span class="keyword">for</span>(<span class="keyword">int</span> i=st;i&lt;=ed;i++) <span class="keyword">if</span>(dfn[i]==<span class="number">0</span>) tarjan(i);</div><div class="line"></div><div class="line">		<span class="keyword">int</span> tot=<span class="number">0</span>;</div><div class="line">		<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=ct;i++)</div><div class="line">			tot+=(e[<span class="number">2</span>*(n+m+i<span class="number">-1</span>)+<span class="number">1</span>].c==<span class="number">0</span> or belg[xx[i]]==belg[n+yy[i]]);</div><div class="line">		<span class="built_in">printf</span>(<span class="string">"%d\n"</span>,ct-tot);</div><div class="line">		<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=ct;i++)</div><div class="line">			<span class="keyword">if</span>(e[<span class="number">2</span>*(n+m+i<span class="number">-1</span>)+<span class="number">1</span>].c==<span class="number">0</span> or belg[xx[i]]==belg[n+yy[i]]) ;</div><div class="line">			<span class="keyword">else</span> <span class="built_in">printf</span>(<span class="string">"%d "</span>,i);</div><div class="line">	&#125;</div><div class="line">&#125;;</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></div><div class="line"></span>&#123;</div><div class="line">	mine::main();</div><div class="line">&#125;</div></pre></td></tr></table></figure></p>

</div></div></p>
<h3 id="20-Poj3422-Kaka’s-Matrix-Travels"><a href="#20-Poj3422-Kaka’s-Matrix-Travels" class="headerlink" title="20 Poj3422 Kaka’s Matrix Travels"></a>20 Poj3422 Kaka’s Matrix Travels</h3><p>9.10 难度1<br><div><div class="fold_hider"><div class="close hider_title">请先思考后再展开</div></div><div class="fold">
<p>考虑用流量表示路径的移动<br>然后因为每个格子只能取一次，拆一下点<br>$st=&gt;(1,1,0),flow=k,cost=0$<br>$(i,j,0)=&gt;(i,j,1),flow=1,cost=num(i,j)$<br>$(i,j,0)=&gt;(i,j,1),flow=\infty,cost=0$<br>$(i,j,1)=&gt;(i+tx[t],j+ty[t],0),flow=\infty,cost=0$<br>$(n,n,1)=&gt;ed,flow=\infty,cost=0$<br>跑最大费用最大流即可</p>

</div></div></p>
<h2 id="0x6B-图论练习"><a href="#0x6B-图论练习" class="headerlink" title="0x6B 图论练习"></a>0x6B 图论练习</h2><p><a href="http://contest-hunter.org:83/contest/0x6B%E3%80%8C%E5%9B%BE%E8%AE%BA%E3%80%8D%E7%BB%83%E4%B9%A0" target="_blank" rel="noopener">部分题目</a></p>
<h3 id="21-6B02-升降梯上"><a href="#21-6B02-升降梯上" class="headerlink" title="21 6B02 升降梯上"></a>21 6B02 升降梯上</h3><p>9.11 难度1<br><div><div class="fold_hider"><div class="close hider_title">请先思考后再展开</div></div><div class="fold">
<p>把每个点拆成m个操作后的状态，最短路即可<br><figure class="highlight cpp"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div><div class="line">25</div><div class="line">26</div><div class="line">27</div><div class="line">28</div><div class="line">29</div><div class="line">30</div><div class="line">31</div><div class="line">32</div><div class="line">33</div><div class="line">34</div><div class="line">35</div><div class="line">36</div><div class="line">37</div><div class="line">38</div><div class="line">39</div><div class="line">40</div><div class="line">41</div><div class="line">42</div><div class="line">43</div><div class="line">44</div><div class="line">45</div><div class="line">46</div><div class="line">47</div><div class="line">48</div><div class="line">49</div><div class="line">50</div><div class="line">51</div><div class="line">52</div><div class="line">53</div><div class="line">54</div><div class="line">55</div><div class="line">56</div><div class="line">57</div><div class="line">58</div><div class="line">59</div><div class="line">60</div><div class="line">61</div><div class="line">62</div><div class="line">63</div><div class="line">64</div><div class="line">65</div><div class="line">66</div><div class="line">67</div><div class="line">68</div><div class="line">69</div><div class="line">70</div><div class="line">71</div><div class="line">72</div><div class="line">73</div><div class="line">74</div><div class="line">75</div><div class="line">76</div><div class="line">77</div><div class="line">78</div><div class="line">79</div><div class="line">80</div><div class="line">81</div><div class="line">82</div><div class="line">83</div><div class="line">84</div><div class="line">85</div><div class="line">86</div><div class="line">87</div><div class="line">88</div></pre></td><td class="code"><pre><div class="line"><span class="comment">//Zory-2018</span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;cmath&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;cstdio&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;cstring&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;cstdlib&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;map&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;set&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;queue&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;deque&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;bitset&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;vector&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;algorithm&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;iostream&gt;</span></span></div><div class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</div><div class="line"></div><div class="line"><span class="keyword">namespace</span> mine</div><div class="line">&#123;</div><div class="line">	<span class="keyword">const</span> <span class="keyword">int</span> MAX_N=<span class="number">21000</span>;</div><div class="line">	<span class="keyword">const</span> <span class="keyword">int</span> INF=<span class="number">0x3f3f3f3f</span>;</div><div class="line">	<span class="function"><span class="keyword">int</span> <span class="title">myabs</span><span class="params">(<span class="keyword">int</span> x)</span> </span>&#123;<span class="keyword">return</span> x&gt;<span class="number">0</span>?x:-x;&#125;</div><div class="line"></div><div class="line">	<span class="keyword">struct</span> Nod</div><div class="line">	&#123;</div><div class="line">		<span class="keyword">int</span> hou;</div><div class="line">		<span class="keyword">int</span> dis;</div><div class="line">		Nod() &#123;hou=<span class="number">0</span>;dis=INF;&#125;</div><div class="line">	&#125;p[MAX_N];</div><div class="line">	<span class="keyword">struct</span> Edge</div><div class="line">	&#123;</div><div class="line">		<span class="keyword">int</span> y,c,g;</div><div class="line">	&#125;e[MAX_N*<span class="number">30</span>];</div><div class="line">	<span class="keyword">int</span> ln=<span class="number">0</span>;<span class="function"><span class="keyword">void</span> <span class="title">ins</span><span class="params">(<span class="keyword">int</span> x,<span class="keyword">int</span> y,<span class="keyword">int</span> c)</span> </span>&#123;e[++ln]=(Edge)&#123;y,c,p[x].hou&#125;;p[x].hou=ln;&#125;</div><div class="line"></div><div class="line">	<span class="keyword">int</span> st,ed;</div><div class="line">	<span class="keyword">struct</span> Data</div><div class="line">	&#123;</div><div class="line">		<span class="keyword">int</span> dis,id;</div><div class="line">		<span class="keyword">friend</span> <span class="keyword">bool</span> <span class="keyword">operator</span> &gt; (Data a,Data b) &#123;<span class="keyword">return</span> a.dis&gt;b.dis;&#125;</div><div class="line">	&#125;;</div><div class="line">	priority_queue&lt; Data,<span class="built_in">vector</span>&lt;Data&gt;,greater&lt;Data&gt; &gt; q;</div><div class="line">	<span class="function"><span class="keyword">void</span> <span class="title">dijkstra</span><span class="params">()</span></div><div class="line">	</span>&#123;</div><div class="line">		p[st].dis=<span class="number">0</span>;q.push((Data)&#123;p[st].dis,st&#125;);</div><div class="line">		<span class="keyword">while</span>(!q.empty())</div><div class="line">		&#123;</div><div class="line">			Data t=q.top();q.pop();</div><div class="line">			<span class="keyword">int</span> x=t.id;<span class="keyword">if</span>(p[x].dis&lt;t.dis) <span class="keyword">continue</span>;</div><div class="line">			<span class="keyword">for</span>(<span class="keyword">int</span> k=p[x].hou;k&gt;<span class="number">0</span>;k=e[k].g)</div><div class="line">			&#123;</div><div class="line">				<span class="keyword">int</span> y=e[k].y;</div><div class="line">				<span class="keyword">if</span>(p[y].dis&gt;p[x].dis+e[k].c)</div><div class="line">				&#123;</div><div class="line">					p[y].dis=p[x].dis+e[k].c;</div><div class="line">					q.push((Data)&#123;p[y].dis,y&#125;);</div><div class="line">				&#125;</div><div class="line">			&#125;</div><div class="line">		&#125;</div><div class="line">	&#125;</div><div class="line"></div><div class="line">	<span class="keyword">int</span> n,m;</div><div class="line">	<span class="keyword">int</span> c[<span class="number">30</span>];</div><div class="line">	<span class="function"><span class="keyword">int</span> <span class="title">calc</span><span class="params">(<span class="keyword">int</span> x,<span class="keyword">int</span> y)</span> </span>&#123;<span class="keyword">return</span> (x<span class="number">-1</span>)*m+y;&#125;</div><div class="line">	<span class="function"><span class="keyword">void</span> <span class="title">main</span><span class="params">()</span></div><div class="line">	</span>&#123;</div><div class="line">		<span class="built_in">scanf</span>(<span class="string">"%d%d"</span>,&amp;n,&amp;m);</div><div class="line">		st=<span class="number">0</span>;ed=n*m+<span class="number">1</span>;</div><div class="line">		<span class="keyword">for</span>(<span class="keyword">int</span> j=<span class="number">1</span>;j&lt;=m;j++)</div><div class="line">		&#123;</div><div class="line">			<span class="built_in">scanf</span>(<span class="string">"%d"</span>,&amp;c[j]);</div><div class="line">			<span class="keyword">if</span>(c[j]==<span class="number">0</span>) ins(st,calc(<span class="number">1</span>,j),<span class="number">0</span>);</div><div class="line">		&#125;</div><div class="line"></div><div class="line">		<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;n;i++)</div><div class="line">			<span class="keyword">for</span>(<span class="keyword">int</span> j=<span class="number">1</span>;j&lt;=m;j++)</div><div class="line">				<span class="keyword">for</span>(<span class="keyword">int</span> k=<span class="number">1</span>;k&lt;=m;k++)</div><div class="line">					<span class="keyword">if</span>(<span class="number">1</span>&lt;=i+c[k] and i+c[k]&lt;=n)</div><div class="line">						ins(calc(i,j),calc(i+c[k],k),myabs(j-k)+<span class="number">2</span>*myabs(c[k]));</div><div class="line">		<span class="keyword">for</span>(<span class="keyword">int</span> j=<span class="number">1</span>;j&lt;=m;j++) ins(calc(n,j),ed,<span class="number">0</span>);</div><div class="line"></div><div class="line">		dijkstra();</div><div class="line">		<span class="built_in">printf</span>(<span class="string">"%d"</span>,p[ed].dis==INF?<span class="number">-1</span>:p[ed].dis);</div><div class="line">	&#125;</div><div class="line">&#125;;</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></div><div class="line"></span>&#123;</div><div class="line">	mine::main();</div><div class="line">&#125;</div></pre></td></tr></table></figure></p>

</div></div></p>
<h3 id="22-NOI2007-社交网络"><a href="#22-NOI2007-社交网络" class="headerlink" title="22 NOI2007 社交网络"></a>22 NOI2007 社交网络</h3><p>9.11 难度2<br><div><div class="fold_hider"><div class="close hider_title">请先思考后再展开</div></div><div class="fold">
<p>原来最短路路径数是可以用floyd统计的<br>然后记住一定要去除编号相同的情况（以前总是偷懒）<br>还有就是，一开始总是想不通怎么处理一条链的情况，为什么不会重复统计呢？<br>但其实，由于其dp性质，一条路径只会在k为最大编号时才被统计<br><figure class="highlight cpp"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div><div class="line">25</div><div class="line">26</div><div class="line">27</div><div class="line">28</div><div class="line">29</div><div class="line">30</div><div class="line">31</div><div class="line">32</div><div class="line">33</div><div class="line">34</div><div class="line">35</div><div class="line">36</div><div class="line">37</div><div class="line">38</div><div class="line">39</div><div class="line">40</div><div class="line">41</div><div class="line">42</div><div class="line">43</div><div class="line">44</div><div class="line">45</div><div class="line">46</div><div class="line">47</div><div class="line">48</div><div class="line">49</div><div class="line">50</div><div class="line">51</div><div class="line">52</div><div class="line">53</div><div class="line">54</div><div class="line">55</div><div class="line">56</div><div class="line">57</div><div class="line">58</div><div class="line">59</div><div class="line">60</div><div class="line">61</div><div class="line">62</div><div class="line">63</div><div class="line">64</div></pre></td><td class="code"><pre><div class="line"><span class="comment">//Zory-2018</span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;cmath&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;cstdio&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;cstring&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;cstdlib&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;map&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;set&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;queue&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;deque&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;bitset&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;vector&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;algorithm&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;iostream&gt;</span></span></div><div class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</div><div class="line"></div><div class="line"><span class="keyword">namespace</span> mine</div><div class="line">&#123;</div><div class="line">	<span class="keyword">const</span> <span class="keyword">int</span> MAX_N=<span class="number">110</span>;</div><div class="line">	<span class="keyword">typedef</span> <span class="keyword">long</span> <span class="keyword">long</span> ll;</div><div class="line"></div><div class="line">	<span class="keyword">int</span> mp[MAX_N][MAX_N];</div><div class="line">	ll cnt[MAX_N][MAX_N];</div><div class="line">	<span class="function"><span class="keyword">void</span> <span class="title">main</span><span class="params">()</span></div><div class="line">	</span>&#123;</div><div class="line">		<span class="built_in">memset</span>(mp,<span class="number">0x3f</span>,<span class="keyword">sizeof</span> mp);</div><div class="line"></div><div class="line">		<span class="keyword">int</span> n,m;<span class="built_in">scanf</span>(<span class="string">"%d%d"</span>,&amp;n,&amp;m);</div><div class="line">		<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=n;i++) mp[i][i]=<span class="number">0</span>,cnt[i][i]=<span class="number">1</span>;</div><div class="line">		<span class="keyword">while</span>(m--)</div><div class="line">		&#123;</div><div class="line">			<span class="keyword">int</span> x,y,c;<span class="built_in">scanf</span>(<span class="string">"%d%d%d"</span>,&amp;x,&amp;y,&amp;c);</div><div class="line">			mp[x][y]=mp[y][x]=c;</div><div class="line">			cnt[x][y]=cnt[y][x]=<span class="number">1</span>;</div><div class="line">		&#125;</div><div class="line">		<span class="comment">//因为floyd的dp性质，左右两边只经过小于当前编号的节点，所以不会计算重复</span></div><div class="line">		<span class="keyword">for</span>(<span class="keyword">int</span> k=<span class="number">1</span>;k&lt;=n;k++)</div><div class="line">			<span class="keyword">for</span>(<span class="keyword">int</span> x=<span class="number">1</span>;x&lt;=n;x++) <span class="keyword">if</span>(x!=k)<span class="comment">//避免重复情况</span></div><div class="line">				<span class="keyword">for</span>(<span class="keyword">int</span> y=<span class="number">1</span>;y&lt;=n;y++) <span class="keyword">if</span>(y!=k and y!=x)</div><div class="line">				&#123;</div><div class="line">					<span class="keyword">if</span>(mp[x][y]&gt;mp[x][k]+mp[k][y])</div><div class="line">					&#123;</div><div class="line">						mp[x][y]=mp[x][k]+mp[k][y];</div><div class="line">						cnt[x][y]=cnt[x][k]*cnt[k][y];</div><div class="line">					&#125;</div><div class="line">					<span class="keyword">else</span> <span class="keyword">if</span>(mp[x][y]==mp[x][k]+mp[k][y])</div><div class="line">						cnt[x][y]+=cnt[x][k]*cnt[k][y];</div><div class="line">				&#125;</div><div class="line"></div><div class="line">		<span class="keyword">for</span>(<span class="keyword">int</span> x=<span class="number">1</span>;x&lt;=n;x++)</div><div class="line">		&#123;</div><div class="line">			<span class="keyword">double</span> ans=<span class="number">0</span>;</div><div class="line">			<span class="keyword">for</span>(<span class="keyword">int</span> st=<span class="number">1</span>;st&lt;=n;st++) <span class="keyword">if</span>(st!=x)</div><div class="line">				<span class="keyword">for</span>(<span class="keyword">int</span> ed=<span class="number">1</span>;ed&lt;=n;ed++) <span class="keyword">if</span>(ed!=x)</div><div class="line">					<span class="keyword">if</span>(mp[st][x]+mp[x][ed]==mp[st][ed])</div><div class="line">						ans+=(<span class="keyword">double</span>)cnt[st][x]*cnt[x][ed]/cnt[st][ed];</div><div class="line">			<span class="built_in">printf</span>(<span class="string">"%.3lf\n"</span>,ans);</div><div class="line">		&#125;</div><div class="line">	&#125;</div><div class="line">&#125;;</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></div><div class="line"></span>&#123;</div><div class="line">	mine::main();</div><div class="line">&#125;</div></pre></td></tr></table></figure></p>

</div></div></p>
<h3 id="23-NOI2003-逃学的小孩"><a href="#23-NOI2003-逃学的小孩" class="headerlink" title="23 NOI2003 逃学的小孩"></a>23 NOI2003 逃学的小孩</h3><p>9.12 难度2<br><div><div class="fold_hider"><div class="close hider_title">请先思考后再展开</div></div><div class="fold">
<p>说来惭愧，其实不难<br>最小化答案：min(c-&gt;a,c-&gt;b)+a-&gt;b<br>然后因为所有直径都是等效的，可以证明a-&gt;b的增加，左边不会降低<br>所以说，直接取a-&gt;b为直径，然后扫描一下就好了</p>

</div></div></p>
<h3 id="24-AHOI2008-紧急集合"><a href="#24-AHOI2008-紧急集合" class="headerlink" title="24 AHOI2008 紧急集合"></a>24 AHOI2008 紧急集合</h3><p>9.12 难度2<br><div><div class="fold_hider"><div class="close hider_title">请先思考后再展开</div></div><div class="fold">
<p>又感到很惭愧了……<br>想了些数据，发现一定是跑到其中一个lca<br>然后又yy几个情况，发现都是应该找深度最小那两个，然后到他们的lca，就不用枚举三次了<br>然后就秒wa了<br>然后就被rose秒出hack数据了，就是深度大那个点在它们到lca之间的路径上……<br>所以最后还是枚举，发现有点慢，最大0.93s……<br>所以正解应该是用离线lca算法，不过太复杂就不改了，大概yy了一下算法权当复习</p>
<p>下面就只给出朴素代码<br><figure class="highlight cpp"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div><div class="line">25</div><div class="line">26</div><div class="line">27</div><div class="line">28</div><div class="line">29</div><div class="line">30</div><div class="line">31</div><div class="line">32</div><div class="line">33</div><div class="line">34</div><div class="line">35</div><div class="line">36</div><div class="line">37</div><div class="line">38</div><div class="line">39</div><div class="line">40</div><div class="line">41</div><div class="line">42</div><div class="line">43</div><div class="line">44</div><div class="line">45</div><div class="line">46</div><div class="line">47</div><div class="line">48</div><div class="line">49</div><div class="line">50</div><div class="line">51</div><div class="line">52</div><div class="line">53</div><div class="line">54</div><div class="line">55</div><div class="line">56</div><div class="line">57</div><div class="line">58</div><div class="line">59</div><div class="line">60</div><div class="line">61</div><div class="line">62</div><div class="line">63</div><div class="line">64</div><div class="line">65</div><div class="line">66</div><div class="line">67</div><div class="line">68</div><div class="line">69</div><div class="line">70</div><div class="line">71</div><div class="line">72</div><div class="line">73</div><div class="line">74</div><div class="line">75</div><div class="line">76</div><div class="line">77</div><div class="line">78</div><div class="line">79</div><div class="line">80</div><div class="line">81</div><div class="line">82</div><div class="line">83</div></pre></td><td class="code"><pre><div class="line"><span class="comment">//Zory-2018</span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;cmath&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;cstdio&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;cstring&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;cstdlib&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;map&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;set&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;queue&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;deque&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;bitset&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;vector&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;algorithm&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;iostream&gt;</span></span></div><div class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</div><div class="line"></div><div class="line"><span class="keyword">namespace</span> mine</div><div class="line">&#123;</div><div class="line">	<span class="keyword">const</span> <span class="keyword">int</span> MAX_N=<span class="number">510000</span>;</div><div class="line"></div><div class="line">	<span class="keyword">struct</span> Nod</div><div class="line">	&#123;</div><div class="line">		<span class="keyword">int</span> hou;</div><div class="line">		<span class="keyword">int</span> dep;</div><div class="line">		Nod() &#123;hou=dep=<span class="number">0</span>;&#125;</div><div class="line">	&#125;p[MAX_N];</div><div class="line">	<span class="keyword">struct</span> Edge</div><div class="line">	&#123;</div><div class="line">		<span class="keyword">int</span> y,g;</div><div class="line">	&#125;e[MAX_N*<span class="number">2</span>];</div><div class="line">	<span class="keyword">int</span> ln=<span class="number">0</span>;<span class="function"><span class="keyword">void</span> <span class="title">ins</span><span class="params">(<span class="keyword">int</span> x,<span class="keyword">int</span> y)</span> </span>&#123;e[++ln]=(Edge)&#123;y,p[x].hou&#125;;p[x].hou=ln;&#125;</div><div class="line"></div><div class="line">	<span class="keyword">int</span> bin[<span class="number">21</span>];</div><div class="line">	<span class="keyword">int</span> f[MAX_N][<span class="number">21</span>];</div><div class="line">	<span class="function"><span class="keyword">void</span> <span class="title">pre</span><span class="params">(<span class="keyword">int</span> x,<span class="keyword">int</span> fa)</span></div><div class="line">	</span>&#123;</div><div class="line">		p[x].dep=p[fa].dep+<span class="number">1</span>;</div><div class="line">		f[x][<span class="number">0</span>]=fa;<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;<span class="number">20</span>;i++) f[x][i]=f[f[x][i<span class="number">-1</span>]][i<span class="number">-1</span>];</div><div class="line">		<span class="keyword">for</span>(<span class="keyword">int</span> k=p[x].hou;k&gt;<span class="number">0</span>;k=e[k].g)</div><div class="line">		&#123;</div><div class="line">			<span class="keyword">int</span> y=e[k].y;<span class="keyword">if</span>(y==fa) <span class="keyword">continue</span>;</div><div class="line">			pre(y,x);</div><div class="line">		&#125;</div><div class="line">	&#125;</div><div class="line">	<span class="function"><span class="keyword">int</span> <span class="title">LCA</span><span class="params">(<span class="keyword">int</span> x,<span class="keyword">int</span> y)</span></div><div class="line">	</span>&#123;</div><div class="line">		<span class="keyword">if</span>(p[x].dep&lt;p[y].dep) swap(x,y);</div><div class="line">		<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">20</span>;i&gt;=<span class="number">0</span>;i--) <span class="keyword">if</span>(p[x].dep-p[y].dep&gt;=bin[i]) x=f[x][i];</div><div class="line">		<span class="keyword">if</span>(x==y) <span class="keyword">return</span> x;</div><div class="line">		<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">20</span>;i&gt;=<span class="number">0</span>;i--) <span class="keyword">if</span>(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];</div><div class="line">		<span class="keyword">return</span> f[x][<span class="number">0</span>];</div><div class="line">	&#125;</div><div class="line">	<span class="function"><span class="keyword">int</span> <span class="title">dis</span><span class="params">(<span class="keyword">int</span> x,<span class="keyword">int</span> y)</span> </span>&#123;<span class="keyword">return</span> p[x].dep+p[y].dep<span class="number">-2</span>*p[LCA(x,y)].dep;&#125;</div><div class="line"></div><div class="line">	<span class="function"><span class="keyword">void</span> <span class="title">main</span><span class="params">()</span></div><div class="line">	</span>&#123;</div><div class="line">		bin[<span class="number">0</span>]=<span class="number">1</span>;<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=<span class="number">20</span>;i++) bin[i]=bin[i<span class="number">-1</span>]&lt;&lt;<span class="number">1</span>;</div><div class="line"></div><div class="line">		<span class="keyword">int</span> n,q;<span class="built_in">scanf</span>(<span class="string">"%d%d"</span>,&amp;n,&amp;q);</div><div class="line">		<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=n<span class="number">-1</span>;i++)</div><div class="line">		&#123;</div><div class="line">			<span class="keyword">int</span> a,b;<span class="built_in">scanf</span>(<span class="string">"%d%d"</span>,&amp;a,&amp;b);</div><div class="line">			ins(a,b);ins(b,a);</div><div class="line">		&#125;</div><div class="line">		pre(<span class="number">1</span>,<span class="number">0</span>);</div><div class="line">		<span class="keyword">while</span>(q--)</div><div class="line">		&#123;</div><div class="line">			<span class="keyword">int</span> a,b,c;<span class="built_in">scanf</span>(<span class="string">"%d%d%d"</span>,&amp;a,&amp;b,&amp;c);</div><div class="line">			<span class="keyword">int</span> lca1=LCA(a,b),lca2=LCA(b,c),lca3=LCA(a,c);</div><div class="line">			<span class="keyword">int</span> c1=(p[a].dep-p[lca1].dep)+(p[b].dep-p[lca1].dep)+dis(lca1,c);</div><div class="line">			<span class="keyword">int</span> c2=(p[b].dep-p[lca2].dep)+(p[c].dep-p[lca2].dep)+dis(lca2,a);</div><div class="line">			<span class="keyword">int</span> c3=(p[a].dep-p[lca3].dep)+(p[c].dep-p[lca3].dep)+dis(lca3,b);</div><div class="line"></div><div class="line">			<span class="keyword">if</span>(c1&lt;=c2 and c1&lt;=c3) <span class="built_in">printf</span>(<span class="string">"%d %d\n"</span>,lca1,c1);</div><div class="line">			<span class="keyword">else</span> <span class="keyword">if</span>(c2&lt;=c1 and c2&lt;=c3) <span class="built_in">printf</span>(<span class="string">"%d %d\n"</span>,lca2,c2);</div><div class="line">			<span class="keyword">else</span> <span class="built_in">printf</span>(<span class="string">"%d %d\n"</span>,lca3,c3);</div><div class="line">		&#125;</div><div class="line">	&#125;</div><div class="line">&#125;;</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></div><div class="line"></span>&#123;</div><div class="line">	mine::main();</div><div class="line">&#125;</div></pre></td></tr></table></figure></p>

</div></div></p>
<h3 id="25-poj1275-Cashier-Employment"><a href="#25-poj1275-Cashier-Employment" class="headerlink" title="25 poj1275 Cashier Employment"></a>25 poj1275 Cashier Employment</h3><p>9.13 难度2<br><div><div class="fold_hider"><div class="close hider_title">请先思考后再展开</div></div><div class="fold">
<p>本来想着如果在费用流统计答案的时候不把费用乘以流量，就能让边权只表示使用这条边的费用<br>那么就可以构图，从st到每个人，流量8费用1，然后时间连向ed，流量就是需求量<br>然后发现这样的修改没有用，因为我可能流量在下一条增广路采用，然后费用就被多次统计了……<br>看了眼tag居然是差分约束……</p>
<p>不难想到可以前缀和一下，构造不等式组<br>不过不知道怎么处理环形的情况，好像涉及了三个元<br>$s[i] \geq s[i-1]$<br>$当i leq 7,s[i]+tot-s[i+15] \geq c[i]$<br>$otherwise,s[i]-s[i-8] \geq c[i]$</p>
<p>膜lxj后发现，显然的单调性，二分即可</p>

</div></div></p>
<h3 id="26-6B12-最优高铁环"><a href="#26-6B12-最优高铁环" class="headerlink" title="26 6B12 最优高铁环"></a>26 6B12 最优高铁环</h3><p>9.13 难度2<br><div><div class="fold_hider"><div class="close hider_title">请先思考后再展开</div></div><div class="fold">
<p>连01规划的sb题都不会做了<br>有点担忧……现在才相同专题都这样，感觉后面要更多地做综合题<br>对于有思考环节深度的题目，经常比别人走得浅<br>当别人在关心判正环太慢的时候，我还毫无思路<br>甚至别人以为我没去做例题……</p>
<p>总之这道题为了判断负环的速度，写的是栈spfa<br>如果在初始值为0的情况下，只要存在最长路的松弛，就是产生了正环<br>然后不知为何本机ac提交wa<br><figure class="highlight cpp"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div><div class="line">25</div><div class="line">26</div><div class="line">27</div><div class="line">28</div><div class="line">29</div><div class="line">30</div><div class="line">31</div><div class="line">32</div><div class="line">33</div><div class="line">34</div><div class="line">35</div><div class="line">36</div><div class="line">37</div><div class="line">38</div><div class="line">39</div><div class="line">40</div><div class="line">41</div><div class="line">42</div><div class="line">43</div><div class="line">44</div><div class="line">45</div><div class="line">46</div><div class="line">47</div><div class="line">48</div><div class="line">49</div><div class="line">50</div><div class="line">51</div><div class="line">52</div><div class="line">53</div><div class="line">54</div><div class="line">55</div><div class="line">56</div><div class="line">57</div><div class="line">58</div><div class="line">59</div><div class="line">60</div><div class="line">61</div><div class="line">62</div><div class="line">63</div><div class="line">64</div><div class="line">65</div><div class="line">66</div><div class="line">67</div><div class="line">68</div><div class="line">69</div><div class="line">70</div><div class="line">71</div><div class="line">72</div><div class="line">73</div><div class="line">74</div><div class="line">75</div><div class="line">76</div><div class="line">77</div><div class="line">78</div><div class="line">79</div><div class="line">80</div><div class="line">81</div><div class="line">82</div><div class="line">83</div><div class="line">84</div><div class="line">85</div><div class="line">86</div><div class="line">87</div><div class="line">88</div><div class="line">89</div><div class="line">90</div><div class="line">91</div><div class="line">92</div><div class="line">93</div></pre></td><td class="code"><pre><div class="line"><span class="comment">//Zory-2018</span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;cmath&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;cstdio&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;cstring&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;cstdlib&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;map&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;set&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;queue&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;deque&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;bitset&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;vector&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;algorithm&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;iostream&gt;</span></span></div><div class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</div><div class="line"></div><div class="line"><span class="keyword">namespace</span> mine</div><div class="line">&#123;</div><div class="line">	<span class="keyword">const</span> <span class="keyword">int</span> MAX_N=<span class="number">1100</span>;</div><div class="line">	<span class="keyword">typedef</span> <span class="keyword">long</span> <span class="keyword">long</span> ll;</div><div class="line"></div><div class="line">	<span class="keyword">int</span> hou[<span class="number">5</span>*MAX_N];</div><div class="line">	<span class="keyword">struct</span> Edge</div><div class="line">	&#123;</div><div class="line">		<span class="keyword">int</span> y,g,c;</div><div class="line">	&#125;e[<span class="number">51000</span>];</div><div class="line">	<span class="keyword">int</span> ln=<span class="number">0</span>;<span class="function"><span class="keyword">void</span> <span class="title">ins</span><span class="params">(<span class="keyword">int</span> x,<span class="keyword">int</span> y,<span class="keyword">int</span> c)</span> </span>&#123;e[++ln]=(Edge)&#123;y,hou[x],c&#125;;hou[x]=ln;&#125;</div><div class="line"></div><div class="line">	<span class="keyword">double</span> dis[<span class="number">5</span>*MAX_N];</div><div class="line">	<span class="keyword">bool</span> v[<span class="number">5</span>*MAX_N];</div><div class="line">	<span class="function"><span class="keyword">bool</span> <span class="title">dfs</span><span class="params">(<span class="keyword">int</span> x,<span class="keyword">double</span> mid)</span></div><div class="line">	</span>&#123;</div><div class="line">		v[x]=<span class="number">1</span>;</div><div class="line">		<span class="keyword">for</span>(<span class="keyword">int</span> k=hou[x];k&gt;<span class="number">0</span>;k=e[k].g)</div><div class="line">		&#123;</div><div class="line">			<span class="keyword">int</span> y=e[k].y;</div><div class="line">			<span class="keyword">if</span>(dis[y]&lt;dis[x]+e[k].c-mid)</div><div class="line">			&#123;</div><div class="line">				<span class="keyword">if</span>(v[y]) <span class="keyword">return</span> <span class="number">1</span>;</div><div class="line">				dis[y]=dis[x]+e[k].c-mid;</div><div class="line">				<span class="keyword">if</span>(dfs(y,mid)) <span class="keyword">return</span> <span class="number">1</span>;</div><div class="line">			&#125;</div><div class="line">		&#125;</div><div class="line">		v[x]=<span class="number">0</span>;</div><div class="line">		<span class="keyword">return</span> <span class="number">0</span>;</div><div class="line">	&#125;</div><div class="line">	<span class="function"><span class="keyword">bool</span> <span class="title">check</span><span class="params">(<span class="keyword">double</span> mid)</span></div><div class="line">	</span>&#123;</div><div class="line">		<span class="built_in">memset</span>(v,<span class="number">0</span>,<span class="keyword">sizeof</span> v);</div><div class="line">		<span class="built_in">memset</span>(dis,<span class="number">0</span>,<span class="keyword">sizeof</span> dis);</div><div class="line">		<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=<span class="number">5000</span>;i++) <span class="keyword">if</span>(dfs(i,mid)) <span class="keyword">return</span> <span class="number">1</span>;</div><div class="line">		<span class="keyword">return</span> <span class="number">0</span>;</div><div class="line">	&#125;</div><div class="line">	<span class="keyword">int</span> sum;<span class="keyword">bool</span> bk;</div><div class="line">	<span class="function"><span class="keyword">int</span> <span class="title">getid</span><span class="params">()</span></div><div class="line">	</span>&#123;</div><div class="line">		<span class="keyword">char</span> c=getchar();</div><div class="line">		<span class="keyword">char</span> c2=getchar();<span class="keyword">int</span> t=<span class="number">0</span>;</div><div class="line">		<span class="keyword">while</span>(<span class="string">'0'</span>&lt;=c2 and c2&lt;=<span class="string">'9'</span>) t=t*<span class="number">10</span>+c2-<span class="string">'0'</span>,c2=getchar();</div><div class="line">		bk=(c2==<span class="string">'-'</span>);</div><div class="line">		<span class="keyword">if</span>(c==<span class="string">'S'</span>) &#123;sum+=<span class="number">1000</span>;<span class="keyword">return</span> t;&#125;</div><div class="line">		<span class="keyword">if</span>(c==<span class="string">'G'</span>) &#123;sum+=<span class="number">500</span>;<span class="keyword">return</span> <span class="number">1000</span>+t;&#125;</div><div class="line">		<span class="keyword">if</span>(c==<span class="string">'D'</span>) &#123;sum+=<span class="number">300</span>;<span class="keyword">return</span> <span class="number">2000</span>+t;&#125;</div><div class="line">		<span class="keyword">if</span>(c==<span class="string">'T'</span>) &#123;sum+=<span class="number">200</span>;<span class="keyword">return</span> <span class="number">3000</span>+t;&#125;</div><div class="line">		sum+=<span class="number">150</span>;<span class="keyword">return</span> <span class="number">4000</span>+t;</div><div class="line">	&#125;</div><div class="line">	<span class="function"><span class="keyword">void</span> <span class="title">main</span><span class="params">()</span></div><div class="line">	</span>&#123;</div><div class="line">		<span class="keyword">int</span> m;<span class="built_in">scanf</span>(<span class="string">"%d"</span>,&amp;m);getchar();</div><div class="line">		<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=m;i++)</div><div class="line">		&#123;</div><div class="line">			sum=<span class="number">0</span>;</div><div class="line">			<span class="keyword">int</span> st=getid();</div><div class="line">			<span class="keyword">int</span> ed=getid();</div><div class="line">			<span class="keyword">while</span>(bk) ed=getid();</div><div class="line">			ins(st,ed,sum);</div><div class="line">		&#125;</div><div class="line"></div><div class="line">		ll l=<span class="number">0</span>,r=(ll)<span class="number">1000</span>*<span class="number">20</span>*<span class="number">50000</span>*<span class="number">10</span>,ans=<span class="number">-1</span>;</div><div class="line">		<span class="keyword">while</span>(l&lt;=r)</div><div class="line">		&#123;</div><div class="line">			ll mid=(l+r)&gt;&gt;<span class="number">1</span>;</div><div class="line">			<span class="keyword">if</span>(check((<span class="keyword">double</span>)mid/<span class="number">10</span>)) ans=mid,l=mid+<span class="number">1</span>;</div><div class="line">			<span class="keyword">else</span> r=mid<span class="number">-1</span>;</div><div class="line">		&#125;</div><div class="line">		<span class="keyword">if</span>(ans&lt;<span class="number">0</span>) <span class="built_in">puts</span>(<span class="string">"-1"</span>);</div><div class="line">		<span class="keyword">else</span> <span class="built_in">printf</span>(<span class="string">"%d"</span>,(<span class="keyword">int</span>)round( (<span class="keyword">double</span>)ans/<span class="number">10</span> ));</div><div class="line">	&#125;</div><div class="line">&#125;;</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></div><div class="line"></span>&#123;</div><div class="line">	mine::main();</div><div class="line">&#125;</div></pre></td></tr></table></figure></p>

</div></div></p>
<h3 id="27-HNOI2012-矿场搭建"><a href="#27-HNOI2012-矿场搭建" class="headerlink" title="27 HNOI2012 矿场搭建"></a>27 HNOI2012 矿场搭建</h3><p>9.14 难度2<br><div><div class="fold_hider"><div class="close hider_title">请先思考后再展开</div></div><div class="fold">
<p>显然先求一下割点，求出每个块的组成<br>分析每个块，如果内部没有割点，那么需要两个出口，位置任意，但不重复<br>如果只有一个割点，那么堵掉就凉了，所以要添加出口，而且不能在割点处<br>如果有两个或以上，那么就无需担心，总能够出去<br>综上说述，乘法原理统计一下即可</p>
<p>然后我以为根节点那个特判会影响vdcc的判断，其实只是影响割点……没有好好思考<br>还有就是完全没考虑孤立点，还好这道题不需要<br><figure class="highlight cpp"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div><div class="line">25</div><div class="line">26</div><div class="line">27</div><div class="line">28</div><div class="line">29</div><div class="line">30</div><div class="line">31</div><div class="line">32</div><div class="line">33</div><div class="line">34</div><div class="line">35</div><div class="line">36</div><div class="line">37</div><div class="line">38</div><div class="line">39</div><div class="line">40</div><div class="line">41</div><div class="line">42</div><div class="line">43</div><div class="line">44</div><div class="line">45</div><div class="line">46</div><div class="line">47</div><div class="line">48</div><div class="line">49</div><div class="line">50</div><div class="line">51</div><div class="line">52</div><div class="line">53</div><div class="line">54</div><div class="line">55</div><div class="line">56</div><div class="line">57</div><div class="line">58</div><div class="line">59</div><div class="line">60</div><div class="line">61</div><div class="line">62</div><div class="line">63</div><div class="line">64</div><div class="line">65</div><div class="line">66</div><div class="line">67</div><div class="line">68</div><div class="line">69</div><div class="line">70</div><div class="line">71</div><div class="line">72</div><div class="line">73</div><div class="line">74</div><div class="line">75</div><div class="line">76</div><div class="line">77</div><div class="line">78</div><div class="line">79</div><div class="line">80</div><div class="line">81</div><div class="line">82</div><div class="line">83</div><div class="line">84</div><div class="line">85</div><div class="line">86</div><div class="line">87</div><div class="line">88</div><div class="line">89</div><div class="line">90</div><div class="line">91</div><div class="line">92</div><div class="line">93</div><div class="line">94</div><div class="line">95</div><div class="line">96</div><div class="line">97</div><div class="line">98</div><div class="line">99</div><div class="line">100</div><div class="line">101</div><div class="line">102</div><div class="line">103</div><div class="line">104</div><div class="line">105</div></pre></td><td class="code"><pre><div class="line"><span class="comment">//Zory-2018</span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;cmath&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;cstdio&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;cstring&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;cstdlib&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;map&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;set&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;queue&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;deque&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;bitset&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;vector&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;algorithm&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;iostream&gt;</span></span></div><div class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</div><div class="line"></div><div class="line"><span class="keyword">namespace</span> mine</div><div class="line">&#123;</div><div class="line">	<span class="keyword">const</span> <span class="keyword">int</span> MAX_N=<span class="number">110000</span>;</div><div class="line">	<span class="keyword">typedef</span> <span class="keyword">long</span> <span class="keyword">long</span> ll;</div><div class="line">	<span class="function"><span class="keyword">int</span> <span class="title">mymin</span><span class="params">(<span class="keyword">int</span> x,<span class="keyword">int</span> y)</span> </span>&#123;<span class="keyword">return</span> x&lt;y?x:y;&#125;</div><div class="line">	<span class="function"><span class="keyword">int</span> <span class="title">mymax</span><span class="params">(<span class="keyword">int</span> x,<span class="keyword">int</span> y)</span> </span>&#123;<span class="keyword">return</span> x&gt;y?x:y;&#125;</div><div class="line"></div><div class="line">	<span class="keyword">int</span> hou[MAX_N];</div><div class="line">	<span class="keyword">struct</span> Edge</div><div class="line">	&#123;</div><div class="line">		<span class="keyword">int</span> y,g;</div><div class="line">	&#125;e[MAX_N];</div><div class="line">	<span class="function"><span class="keyword">int</span> <span class="title">oth</span><span class="params">(<span class="keyword">int</span> x)</span> </span>&#123;<span class="keyword">return</span> x&amp;<span class="number">1</span>?x+<span class="number">1</span>:x<span class="number">-1</span>;&#125;</div><div class="line">	<span class="keyword">int</span> ln;<span class="function"><span class="keyword">void</span> <span class="title">ins</span><span class="params">(<span class="keyword">int</span> x,<span class="keyword">int</span> y)</span> </span>&#123;e[++ln]=(Edge)&#123;y,hou[x]&#125;;hou[x]=ln;&#125;</div><div class="line"></div><div class="line">	<span class="keyword">int</span> cnt;<span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; vdcc[MAX_N];</div><div class="line">	<span class="keyword">bool</span> gd[MAX_N];</div><div class="line">	<span class="keyword">int</span> id,dfn[MAX_N],low[MAX_N];</div><div class="line">	<span class="keyword">int</span> sta[MAX_N],top;<span class="keyword">bool</span> insta[MAX_N];</div><div class="line">	<span class="function"><span class="keyword">void</span> <span class="title">tarjan</span><span class="params">(<span class="keyword">int</span> x,<span class="keyword">int</span> fm)</span></div><div class="line">	</span>&#123;</div><div class="line">		sta[++top]=x;insta[x]=<span class="number">1</span>;</div><div class="line">		dfn[x]=low[x]=++id;</div><div class="line">		<span class="keyword">int</span> son=<span class="number">0</span>;<span class="comment">//debug 这个不能影响vdcc的判定条件，只是和是否割点有关</span></div><div class="line">		<span class="keyword">for</span>(<span class="keyword">int</span> k=hou[x];k&gt;<span class="number">0</span>;k=e[k].g)</div><div class="line">		&#123;</div><div class="line">			<span class="keyword">int</span> y=e[k].y;<span class="keyword">if</span>(k==oth(fm)) <span class="keyword">continue</span>;</div><div class="line">			<span class="keyword">if</span>(dfn[y]==<span class="number">0</span>)</div><div class="line">			&#123;</div><div class="line">				tarjan(y,k);low[x]=mymin(low[x],low[y]);</div><div class="line">				<span class="keyword">if</span>(low[y]&gt;=dfn[x] or (fm==<span class="number">0</span> and son&gt;=<span class="number">2</span>))<span class="comment">//块</span></div><div class="line">				&#123;</div><div class="line">					son++;vdcc[++cnt].clear();</div><div class="line">					<span class="keyword">if</span>(fm!=<span class="number">0</span> or son&gt;=<span class="number">2</span>) gd[x]=<span class="number">1</span>;</div><div class="line">					<span class="keyword">while</span>(<span class="number">1</span>)</div><div class="line">					&#123;</div><div class="line">						<span class="keyword">int</span> now=sta[top--];</div><div class="line">						vdcc[cnt].push_back(now);</div><div class="line">						<span class="keyword">if</span>(now==y) <span class="keyword">break</span>;</div><div class="line">					&#125;</div><div class="line">					vdcc[cnt].push_back(x);</div><div class="line">				&#125;</div><div class="line">			&#125;</div><div class="line">			<span class="keyword">else</span> <span class="keyword">if</span>(insta[y]) low[x]=mymin(low[x],dfn[y]);</div><div class="line">		&#125;</div><div class="line"></div><div class="line">		<span class="comment">//debug 注意我忘记考虑孤立点的情况了</span></div><div class="line">		<span class="comment">//但因为这道题没有自环，也确实不用考虑</span></div><div class="line">	&#125;</div><div class="line"></div><div class="line">	<span class="function"><span class="keyword">void</span> <span class="title">main</span><span class="params">()</span></div><div class="line">	</span>&#123;</div><div class="line">		<span class="keyword">int</span> ct=<span class="number">0</span>;</div><div class="line">		<span class="keyword">while</span>(<span class="number">1</span>)</div><div class="line">		&#123;</div><div class="line">			<span class="keyword">int</span> n;<span class="built_in">scanf</span>(<span class="string">"%d"</span>,&amp;n);</div><div class="line">			<span class="keyword">if</span>(n==<span class="number">0</span>) <span class="keyword">break</span>;</div><div class="line"></div><div class="line">			ln=<span class="number">0</span>;<span class="built_in">memset</span>(hou,<span class="number">0</span>,<span class="keyword">sizeof</span> hou);</div><div class="line">			<span class="keyword">int</span> mx=<span class="number">0</span>;</div><div class="line">			<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=n;i++)</div><div class="line">			&#123;</div><div class="line">				<span class="keyword">int</span> x,y;<span class="built_in">scanf</span>(<span class="string">"%d%d"</span>,&amp;x,&amp;y);</div><div class="line">				ins(x,y);ins(y,x);</div><div class="line">				mx=mymax(mx,mymax(x,y));</div><div class="line">			&#125;</div><div class="line"></div><div class="line">			id=top=cnt=<span class="number">0</span>;</div><div class="line">			<span class="built_in">memset</span>(insta,<span class="number">0</span>,<span class="keyword">sizeof</span> insta);</div><div class="line">			<span class="built_in">memset</span>(gd,<span class="number">0</span>,<span class="keyword">sizeof</span> gd);</div><div class="line">			<span class="built_in">memset</span>(dfn,<span class="number">0</span>,<span class="keyword">sizeof</span> dfn);</div><div class="line">			<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=mx;i++) <span class="keyword">if</span>(dfn[i]==<span class="number">0</span>) tarjan(i,<span class="number">0</span>);</div><div class="line"></div><div class="line">			ll tot=<span class="number">0</span>,ans=<span class="number">1</span>;</div><div class="line">			<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=cnt;i++)</div><div class="line">			&#123;</div><div class="line">				<span class="keyword">int</span> siz=vdcc[i].size();</div><div class="line">				<span class="keyword">int</span> dg=<span class="number">0</span>;<span class="keyword">for</span>(<span class="keyword">int</span> j=<span class="number">0</span>;j&lt;siz;j++) <span class="keyword">if</span>(gd[vdcc[i][j]]) dg++;</div><div class="line">				<span class="keyword">if</span>(dg==<span class="number">0</span>) tot+=<span class="number">2</span>,ans*=(ll)siz*(siz<span class="number">-1</span>)/<span class="number">2</span>;</div><div class="line">				<span class="keyword">if</span>(dg==<span class="number">1</span>) tot++,ans*=siz<span class="number">-1</span>;</div><div class="line">			&#125;</div><div class="line">			<span class="built_in">printf</span>(<span class="string">"Case %d: %lld %lld\n"</span>,++ct,tot,ans);</div><div class="line">		&#125;</div><div class="line">	&#125;</div><div class="line">&#125;;</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></div><div class="line"></span>&#123;</div><div class="line">	mine::main();</div><div class="line">&#125;</div></pre></td></tr></table></figure></p>

</div></div></p>
<h3 id="28-bzoj3033-太鼓达人"><a href="#28-bzoj3033-太鼓达人" class="headerlink" title="28 bzoj3033 太鼓达人"></a>28 bzoj3033 太鼓达人</h3><p>9.15 难度2<br><div><div class="fold_hider"><div class="close hider_title">请先思考后再展开</div></div><div class="fold">
<p>非常好的一道题，如果lxj不说是欧拉图我肯定不会做……<br>先考虑长度，显然不会超过 $2^k$ ，否则一定会出现重复<br>那么如果我们能构造出一种方案，保证长度为 $2^k$ ，那么答案就是 $2^k$</p>
<p>假设该结论成立，那么我们需要覆盖 0~ $2^k-1$ 的每个值<br>有一个不那么好像的方法，但因为自己受到提示，不难想到把每个值作为边<br>然后为了确保出现的独一无二，分割为前面k-1个和后面k-1个，转移的边为了字典序优先选最小的<br>那么因为出度为2，入度为2，一定是一个欧拉图，那么一定能得出 $2^k$ 的长度0</p>
<p>如果讲得不清楚，这位女选手的<a href="https://blog.csdn.net/Clove_unique/article/details/70160122" target="_blank" rel="noopener">图片</a>不错</p>

</div></div></p>
<h3 id="29-中山市选-杀人游戏"><a href="#29-中山市选-杀人游戏" class="headerlink" title="29 中山市选 杀人游戏"></a>29 中山市选 杀人游戏</h3><p>9.15 难度1<br><div><div class="fold_hider"><div class="close hider_title">请先思考后再展开</div></div><div class="fold">
<p>这道题的题意不太清晰<br>其实就是尽量少去交给命运决定……（少尝试）<br>答案就是 $\frac{n-尝试数量}{n}$ ，也就是都不是杀手<br>那么缩点后找入度为0即可<br>不过如果本来是一个点，那么可以用排除法得出结果，稍微判断一下即可</p>

</div></div></p>
<h3 id="30-poj3648-Wedding"><a href="#30-poj3648-Wedding" class="headerlink" title="30 poj3648 Wedding"></a>30 poj3648 Wedding</h3><p>9.15 难度1<br><div><div class="fold_hider"><div class="close hider_title">请先思考后再展开</div></div><div class="fold">
<p>2-sat比较显然<br>假设新娘在右边，然后左边不能有通奸，直接scc判断即可<br>那么因为有可能新郎也通奸，导致新娘去左边了，<br>为了防止这种情况，从新娘到新郎连一条边表示非法性<br><figure class="highlight cpp"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div><div class="line">25</div><div class="line">26</div><div class="line">27</div><div class="line">28</div><div class="line">29</div><div class="line">30</div><div class="line">31</div><div class="line">32</div><div class="line">33</div><div class="line">34</div><div class="line">35</div><div class="line">36</div><div class="line">37</div><div class="line">38</div><div class="line">39</div><div class="line">40</div><div class="line">41</div><div class="line">42</div><div class="line">43</div><div class="line">44</div><div class="line">45</div><div class="line">46</div><div class="line">47</div><div class="line">48</div><div class="line">49</div><div class="line">50</div><div class="line">51</div><div class="line">52</div><div class="line">53</div><div class="line">54</div><div class="line">55</div><div class="line">56</div><div class="line">57</div><div class="line">58</div><div class="line">59</div><div class="line">60</div><div class="line">61</div><div class="line">62</div><div class="line">63</div><div class="line">64</div><div class="line">65</div><div class="line">66</div><div class="line">67</div><div class="line">68</div><div class="line">69</div><div class="line">70</div><div class="line">71</div><div class="line">72</div><div class="line">73</div><div class="line">74</div><div class="line">75</div><div class="line">76</div><div class="line">77</div><div class="line">78</div><div class="line">79</div><div class="line">80</div><div class="line">81</div><div class="line">82</div><div class="line">83</div><div class="line">84</div><div class="line">85</div><div class="line">86</div><div class="line">87</div><div class="line">88</div><div class="line">89</div><div class="line">90</div><div class="line">91</div><div class="line">92</div><div class="line">93</div><div class="line">94</div><div class="line">95</div><div class="line">96</div><div class="line">97</div><div class="line">98</div><div class="line">99</div><div class="line">100</div></pre></td><td class="code"><pre><div class="line"><span class="comment">//Zory-2018</span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;cmath&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;cstdio&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;cstring&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;cstdlib&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;map&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;set&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;queue&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;deque&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;bitset&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;vector&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;algorithm&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;iostream&gt;</span></span></div><div class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</div><div class="line"></div><div class="line"><span class="keyword">namespace</span> mine</div><div class="line">&#123;</div><div class="line">	<span class="keyword">const</span> <span class="keyword">int</span> MAX_N=<span class="number">110000</span>;</div><div class="line">	<span class="keyword">typedef</span> <span class="keyword">long</span> <span class="keyword">long</span> ll;</div><div class="line">	<span class="function"><span class="keyword">int</span> <span class="title">mymin</span><span class="params">(<span class="keyword">int</span> x,<span class="keyword">int</span> y)</span> </span>&#123;<span class="keyword">return</span> x&lt;y?x:y;&#125;</div><div class="line">	<span class="function"><span class="keyword">int</span> <span class="title">mymax</span><span class="params">(<span class="keyword">int</span> x,<span class="keyword">int</span> y)</span> </span>&#123;<span class="keyword">return</span> x&gt;y?x:y;&#125;</div><div class="line"></div><div class="line">	<span class="keyword">int</span> hou[MAX_N];</div><div class="line">	<span class="keyword">struct</span> Edge</div><div class="line">	&#123;</div><div class="line">		<span class="keyword">int</span> y,g;</div><div class="line">	&#125;e[MAX_N];</div><div class="line">	<span class="keyword">int</span> ln;<span class="function"><span class="keyword">void</span> <span class="title">ins</span><span class="params">(<span class="keyword">int</span> x,<span class="keyword">int</span> y)</span> </span>&#123;e[++ln]=(Edge)&#123;y,hou[x]&#125;;hou[x]=ln;&#125;</div><div class="line"></div><div class="line">	<span class="keyword">int</span> id,dfn[MAX_N],low[MAX_N];</div><div class="line">	<span class="keyword">int</span> cnt,belg[MAX_N];</div><div class="line">	<span class="keyword">int</span> sta[MAX_N],top;<span class="keyword">bool</span> insta[MAX_N];</div><div class="line">	<span class="function"><span class="keyword">void</span> <span class="title">tarjan</span><span class="params">(<span class="keyword">int</span> x)</span></div><div class="line">	</span>&#123;</div><div class="line">		sta[++top]=x;insta[x]=<span class="number">1</span>;</div><div class="line">		dfn[x]=low[x]=++id;</div><div class="line">		<span class="keyword">for</span>(<span class="keyword">int</span> k=hou[x];k&gt;<span class="number">0</span>;k=e[k].g)</div><div class="line">		&#123;</div><div class="line">			<span class="keyword">int</span> y=e[k].y;</div><div class="line">			<span class="keyword">if</span>(dfn[y]==<span class="number">0</span>) tarjan(y),low[x]=mymin(low[x],low[y]);</div><div class="line">			<span class="keyword">else</span> <span class="keyword">if</span>(insta[y]) low[x]=mymin(low[x],dfn[y]);</div><div class="line">		&#125;</div><div class="line">		<span class="keyword">if</span>(dfn[x]==low[x])</div><div class="line">		&#123;</div><div class="line">			cnt++;</div><div class="line">			<span class="keyword">while</span>(<span class="number">1</span>)</div><div class="line">			&#123;</div><div class="line">				<span class="keyword">int</span> now=sta[top--];</div><div class="line">				belg[now]=cnt;</div><div class="line">				insta[now]=<span class="number">0</span>;</div><div class="line">				<span class="keyword">if</span>(now==x) <span class="keyword">break</span>;</div><div class="line">			&#125;</div><div class="line">		&#125;</div><div class="line">	&#125;</div><div class="line"></div><div class="line">	<span class="function"><span class="keyword">int</span> <span class="title">getid</span><span class="params">()</span></div><div class="line">	</span>&#123;</div><div class="line">		<span class="keyword">int</span> t;<span class="keyword">char</span> c;<span class="built_in">scanf</span>(<span class="string">"%d%c"</span>,&amp;t,&amp;c);</div><div class="line">		<span class="keyword">return</span> <span class="number">2</span>*t+(c==<span class="string">'h'</span>);<span class="comment">//0~2n-1</span></div><div class="line">	&#125;</div><div class="line">	<span class="function"><span class="keyword">void</span> <span class="title">output</span><span class="params">(<span class="keyword">int</span> x)</span> </span>&#123;<span class="built_in">printf</span>(<span class="string">"%d%c "</span>,x/<span class="number">2</span>,x&amp;<span class="number">1</span>?<span class="string">'h'</span>:<span class="string">'w'</span>);&#125;</div><div class="line">	<span class="keyword">bool</span> v[MAX_N];<span class="comment">//块的选择状态</span></div><div class="line">	<span class="function"><span class="keyword">void</span> <span class="title">main</span><span class="params">()</span></div><div class="line">	</span>&#123;</div><div class="line">		<span class="keyword">while</span>(<span class="number">1</span>)</div><div class="line">		&#123;</div><div class="line">			<span class="keyword">int</span> n,m;<span class="built_in">scanf</span>(<span class="string">"%d%d"</span>,&amp;n,&amp;m);</div><div class="line">			<span class="keyword">if</span>(n==<span class="number">0</span> and m==<span class="number">0</span>) <span class="keyword">break</span>;</div><div class="line"></div><div class="line">			ln=<span class="number">0</span>;<span class="built_in">memset</span>(hou,<span class="number">0</span>,<span class="keyword">sizeof</span> hou);</div><div class="line">			ins(<span class="number">0</span>,<span class="number">1</span>);<span class="comment">//确保选新郎，否则非法</span></div><div class="line">			<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=m;i++)</div><div class="line">			&#123;</div><div class="line">				<span class="keyword">int</span> a=getid(),b=getid();</div><div class="line">				ins(a,b^<span class="number">1</span>);ins(b,a^<span class="number">1</span>);</div><div class="line">			&#125;</div><div class="line">			cnt=<span class="number">0</span>;top=<span class="number">0</span>;id=<span class="number">0</span>;</div><div class="line">			<span class="built_in">memset</span>(dfn,<span class="number">0</span>,<span class="keyword">sizeof</span> dfn);</div><div class="line">			<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;=<span class="number">2</span>*(n<span class="number">-1</span>)+<span class="number">1</span>;i++) <span class="keyword">if</span>(dfn[i]==<span class="number">0</span>) tarjan(i);</div><div class="line"></div><div class="line">			<span class="built_in">memset</span>(v,<span class="number">0</span>,<span class="keyword">sizeof</span> v);</div><div class="line">			<span class="comment">//反图拓扑序小=&gt;正图拓扑序大=&gt;正图scc编号小</span></div><div class="line">			<span class="keyword">bool</span> bk=<span class="number">0</span>;</div><div class="line">			<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;=n<span class="number">-1</span>;i++)</div><div class="line">			&#123;</div><div class="line">				<span class="keyword">int</span> fx=belg[i*<span class="number">2</span>],fy=belg[i*<span class="number">2</span>+<span class="number">1</span>];</div><div class="line">				<span class="keyword">if</span>(fx==fy) bk=<span class="number">1</span>;</div><div class="line">				v[mymin(fx,fy)]=<span class="number">1</span>;</div><div class="line">			&#125;</div><div class="line">			<span class="keyword">if</span>(bk) &#123;<span class="built_in">puts</span>(<span class="string">"bad luck"</span>);<span class="keyword">continue</span>;&#125;</div><div class="line">			<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=n<span class="number">-1</span>;i++) output(v[belg[<span class="number">2</span>*i]]?<span class="number">2</span>*i+<span class="number">1</span>:<span class="number">2</span>*i);<span class="comment">//得出新郎，输出新娘</span></div><div class="line">			<span class="built_in">puts</span>(<span class="string">""</span>);</div><div class="line">		&#125;</div><div class="line">	&#125;</div><div class="line">&#125;;</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></div><div class="line"></span>&#123;</div><div class="line">	mine::main();</div><div class="line">&#125;</div></pre></td></tr></table></figure></p>

</div></div></p>
<h3 id="31-poj1112-Team-Them-Up"><a href="#31-poj1112-Team-Them-Up" class="headerlink" title="31 poj1112 Team Them Up!"></a>31 poj1112 Team Them Up!</h3><p>9.18 难度2<br><div><div class="fold_hider"><div class="close hider_title">请先思考后再展开</div></div><div class="fold">
<p>题目关键：直接认识</p>
<p>在本题中，单一的单向边是没有意义的，应转化为双向边<br>因为这个直接到达有点麻烦，如果取补图，边的意义就是【不能在相同的组中】<br>此时成功产生了互斥关系，可以二分图染色，如果不是二分图，直接无解</p>
<p>当然我们染色出来的只是其中一种解<br>对于每个联通块，都是可以取反的<br>那么现在相当于一个有序二元组，目标就是让人数差最小<br>01背包dp一下，转移很快，滚不滚没关系</p>

</div></div></p>
<h3 id="32-zoj1654-HEOI2016-TJOI2016-游戏"><a href="#32-zoj1654-HEOI2016-TJOI2016-游戏" class="headerlink" title="32 zoj1654/HEOI2016/TJOI2016 游戏"></a>32 zoj1654/HEOI2016/TJOI2016 游戏</h3><p>9.18 难度2<br><div><div class="fold_hider"><div class="close hider_title">请先思考后再展开</div></div><div class="fold">
<p>又没看出来……<br>先想了想网络流，肯定不对<br>因为是双向边，想了想二分图，感觉不对，因为我选，下一个不选，并不代表再下一个会选<br>然后想想2-sat，有点像，但不知道怎么满足最大……</p>
<p>看了看tag，我去，最大独立集<br>好像有道理，但不应该是一般图吗？<br>再想想……<br>哦因为排斥关系是行或列的，所以没有奇环……</p>
<p>然后就连样例都过不去了……<br>随便考虑一行多个点，然后就会有奇环<br>凉了</p>
<p>lxj提示说和草地排水很像<br>一下得到启发，分行块和列块，把点化作边<br>那么每个点最多连一条边，那么就是一个二分图匹配</p>

</div></div></p>

      
    </div>

    
    
    

    
      <div class="post-tags">
        
          <a href="/tags/算法竞赛进阶指南/" rel="tag"># 算法竞赛进阶指南</a>
        
      </div>
    

    
      

  <div class="popular-posts-header">相关文章推荐</div>
  <ul class="popular-posts">
  
    <li class="popular-posts-item">
      
      
      <div class="popular-posts-title"><a href="/posts/18f8.html" rel="bookmark">【训练】算法竞赛进阶指南-5动态规划</a></div>
      
    </li>
  
    <li class="popular-posts-item">
      
      
      <div class="popular-posts-title"><a href="/posts/cfc5.html" rel="bookmark">【训练】算法竞赛进阶指南-0基本算法23题</a></div>
      
    </li>
  
    <li class="popular-posts-item">
      
      
      <div class="popular-posts-title"><a href="/posts/9d2f.html" rel="bookmark">【训练】算法竞赛进阶指南-2搜索13题</a></div>
      
    </li>
  
    <li class="popular-posts-item">
      
      
      <div class="popular-posts-title"><a href="/posts/7248.html" rel="bookmark">【训练】算法竞赛进阶指南-1基本数据结构21题</a></div>
      
    </li>
  
    <li class="popular-posts-item">
      
      
      <div class="popular-posts-title"><a href="/posts/82f7.html" rel="bookmark">【训练】算法竞赛进阶指南-3数学30题</a></div>
      
    </li>
  
  </ul>


    

	
		<div>
				<p id="div-border-left-purple">
			   <b>本文基于<a target="_blank" title="Creative Commons Attribution-ShareAlike 4.0 International (CC BY-SA 4.0)" href="http://creativecommons.org/licenses/by-sa/4.0/deed.zh"> 知识共享署名-相同方式共享 4.0 </a>国际许可协议发布</b><br/>
				<span>
				<b>本文地址：</b><a href="/posts/6259.html" title="【训练】算法竞赛进阶指南-6图论 32题">http://zory.cf/posts/6259.html</a><br/><b>转载请注明出处，谢谢！</b>
				</span>
				</p>
		</div>
    

    
    
    

    

    
      <div>
        <div style="padding: 10px 0; margin: 20px auto; width: 90%; text-align: center;">
  <div>哪怕是一杯奶茶，也将鼓励我继续创作！</div>
  <button id="rewardButton" disable="enable" onclick="var qr = document.getElementById('QR'); if (qr.style.display === 'none') {qr.style.display='block';} else {qr.style.display='none'}">
    <span>打赏</span>
  </button>
  <div id="QR" style="display: none;">

    
      <div id="wechat" style="display: inline-block">
        <img id="wechat_qr" src="/images/wechatpay.png" alt="Zory 微信支付"/>
        <p>微信支付</p>
      </div>
    

    

    

  </div>
</div>

      </div>
    

    

    <footer class="post-footer">
      

      
      
        <div class="post-widgets">
        

        

        
          
          <div id="needsharebutton-postbottom">
            <span class="btn">
              <i class="fa fa-share-alt" aria-hidden="true"></i>
            </span>
          </div>
        
        </div>
      
      

      
        <div class="post-nav">
          <div class="post-nav-next post-nav-item">
            
              <a href="/posts/f4a4.html" rel="next" title="【Arc101D】Median of Medians">
                <i class="fa fa-chevron-left"></i> 【Arc101D】Median of Medians
              </a>
            
          </div>

          <span class="post-nav-divider"></span>

          <div class="post-nav-prev post-nav-item">
            
              <a href="/posts/9f63.html" rel="prev" title="【Arc102b】All Your Paths are Different Lengths">
                【Arc102b】All Your Paths are Different Lengths <i class="fa fa-chevron-right"></i>
              </a>
            
          </div>
        </div>
      

      
      
    </footer>
  </div>
  
  
  
  </article>



    <div class="post-spread">
      
    </div>
  </div>


          </div>
          

  
    <div class="comments" id="comments">
    </div>
  



        </div>
        
          
  
  <div class="sidebar-toggle">
    <div class="sidebar-toggle-line-wrap">
      <span class="sidebar-toggle-line sidebar-toggle-line-first"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-middle"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-last"></span>
    </div>
  </div>

  <aside id="sidebar" class="sidebar">
    
    <div class="sidebar-inner">

      

      
        <ul class="sidebar-nav motion-element">
          <li class="sidebar-nav-toc sidebar-nav-active" data-target="post-toc-wrap">
            文章目录
          </li>
          <li class="sidebar-nav-overview" data-target="site-overview-wrap">
            站点概览
          </li>
        </ul>
      

      <section class="site-overview-wrap sidebar-panel">
        <div class="site-overview">
          <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
            
              <img class="site-author-image" itemprop="image"
                src="http://ouk2t1pgs.bkt.clouddn.com/avatar.jpg"
                alt="Zory" />
            
              <p class="site-author-name" itemprop="name">Zory</p>
              <p class="site-description motion-element" itemprop="description">人生即使不能走最短路，仍是连通图</p>
          </div>

          
            <nav class="site-state motion-element">
              
                <div class="site-state-item site-state-posts">
                
                  <a href="/archives/">
                
                    <span class="site-state-item-count">354</span>
                    <span class="site-state-item-name">文章</span>
                  </a>
                </div>
              

              
                
                
                <div class="site-state-item site-state-categories">
                  <a href="/categories/index.html">
                    
                    
                      
                    
                      
                    
                      
                    
                      
                    
                    <span class="site-state-item-count">4</span>
                    <span class="site-state-item-name">分类</span>
                  </a>
                </div>
              

              
                
                
                <div class="site-state-item site-state-tags">
                  <a href="/tags/index.html">
                    
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                    <span class="site-state-item-count">133</span>
                    <span class="site-state-item-name">标签</span>
                  </a>
                </div>
              
            </nav>
          

          

          
            <div class="links-of-author motion-element">
              
                <span class="links-of-author-item">
                  <a href="https://github.com/Zory123" target="_blank" title="GitHub" rel="external nofollow"><i class="fa fa-fw fa-github"></i>GitHub</a>
                  
                </span>
              
                <span class="links-of-author-item">
                  <a href="mailto:1134430323@qq.com" target="_blank" title="E-Mail" rel="external nofollow"><i class="fa fa-fw fa-envelope"></i>E-Mail</a>
                  
                </span>
              
            </div>
          

          
          

          
          

          
            
          
          

<script type="text/javascript" src="https://api.lwl12.com/hitokoto/main/get?encode=js&charset=utf-8"></script>
<div id="lwlhitokoto">
    <script>
        lwlhitokoto()
    </script>
</div>

        </div>
      </section>

      
      <!--noindex-->
        <section class="post-toc-wrap motion-element sidebar-panel sidebar-panel-active">
          <div class="post-toc">

            
              
            

            
              <div class="post-toc-content"><ol class="nav"><li class="nav-item nav-level-2"><a class="nav-link" href="#0x60-图论"><span class="nav-text">0x60 图论</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#1-poj3662-Telephone-Lines"><span class="nav-text">1 poj3662 Telephone Lines</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#2-noip2009-最优贸易"><span class="nav-text">2 noip2009 最优贸易</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#3-Usaco2011-Jan-Gold-道路和航线"><span class="nav-text">3 Usaco2011 Jan Gold 道路和航线</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#4-poj1734-Sightseeing-trip"><span class="nav-text">4 poj1734 Sightseeing trip</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#5-6201-走廊泼水节"><span class="nav-text">5 6201 走廊泼水节</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#6-poj1639-Picnic-Planning"><span class="nav-text">6 poj1639 Picnic Planning</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#7-poj2728-Desert-King"><span class="nav-text">7 poj2728 Desert King</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#8-APIO2010-巡逻"><span class="nav-text">8 APIO2010 巡逻</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#9-CH-56C-异象石"><span class="nav-text">9 CH#56C 异象石</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#10-BJWC2010-严格次小生成树"><span class="nav-text">10 BJWC2010 严格次小生成树</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#11-IOI2008-Island"><span class="nav-text">11 IOI2008 Island</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#12-6401-创世纪"><span class="nav-text">12 6401 创世纪</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#13-POI2008-BLO-Blockade"><span class="nav-text">13 POI2008 BLO-Blockade</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#14-poj3694-Network"><span class="nav-text">14 poj3694 Network</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#15-poj2942-Knights-of-the-Round-Table"><span class="nav-text">15 poj2942 Knights of the Round Table</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#16-poj1236-Network-of-Schools"><span class="nav-text">16 poj1236 Network of Schools</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#17-poj2226-Muddy-Fields"><span class="nav-text">17 poj2226 Muddy Fields</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#18-6902-Vani和Cl2捉迷藏"><span class="nav-text">18 6902 Vani和Cl2捉迷藏</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#19-CH-17-舞动的夜晚"><span class="nav-text">19 CH#17 舞动的夜晚</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#20-Poj3422-Kaka’s-Matrix-Travels"><span class="nav-text">20 Poj3422 Kaka’s Matrix Travels</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#0x6B-图论练习"><span class="nav-text">0x6B 图论练习</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#21-6B02-升降梯上"><span class="nav-text">21 6B02 升降梯上</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#22-NOI2007-社交网络"><span class="nav-text">22 NOI2007 社交网络</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#23-NOI2003-逃学的小孩"><span class="nav-text">23 NOI2003 逃学的小孩</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#24-AHOI2008-紧急集合"><span class="nav-text">24 AHOI2008 紧急集合</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#25-poj1275-Cashier-Employment"><span class="nav-text">25 poj1275 Cashier Employment</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#26-6B12-最优高铁环"><span class="nav-text">26 6B12 最优高铁环</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#27-HNOI2012-矿场搭建"><span class="nav-text">27 HNOI2012 矿场搭建</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#28-bzoj3033-太鼓达人"><span class="nav-text">28 bzoj3033 太鼓达人</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#29-中山市选-杀人游戏"><span class="nav-text">29 中山市选 杀人游戏</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#30-poj3648-Wedding"><span class="nav-text">30 poj3648 Wedding</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#31-poj1112-Team-Them-Up"><span class="nav-text">31 poj1112 Team Them Up!</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#32-zoj1654-HEOI2016-TJOI2016-游戏"><span class="nav-text">32 zoj1654/HEOI2016/TJOI2016 游戏</span></a></li></ol></li></ol></div>
            

          </div>
        </section>
      <!--/noindex-->
      

      

    </div>
  </aside>


        
      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="footer-inner">
        <div class="copyright">&copy; 2017 &mdash; <span itemprop="copyrightYear">2018</span>
  <span class="with-love" id="animate">
    <i class="fa fa-heart"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">Zory</span>

  

  
</div>


  









  <div class="footer-custom">Hosted by <a target="_blank" rel="external nofollow" href="https://pages.coding.me"><b>Coding Pages</b></a></div>


        








        
      </div>
    </footer>

    
      <div class="back-to-top">
        <i class="fa fa-arrow-up"></i>
        
          <span id="scrollpercent"><span>0</span>%</span>
        
      </div>
    

    

  </div>

  

<script type="text/javascript">
  if (Object.prototype.toString.call(window.Promise) !== '[object Function]') {
    window.Promise = null;
  }
</script>












  















  
  
    <script type="text/javascript" src="/lib/jquery/index.js?v=2.1.3"></script>
  

  
  
    <script type="text/javascript" src="/lib/velocity/velocity.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/lib/velocity/velocity.ui.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/lib/fancybox/source/jquery.fancybox.pack.js?v=2.1.5"></script>
  


  


  <script type="text/javascript" src="/js/src/utils.js?v=6.3.0"></script>

  <script type="text/javascript" src="/js/src/motion.js?v=6.3.0"></script>



  
  

  
  <script type="text/javascript" src="/js/src/scrollspy.js?v=6.3.0"></script>
<script type="text/javascript" src="/js/src/post-details.js?v=6.3.0"></script>



  


  <script type="text/javascript" src="/js/src/bootstrap.js?v=6.3.0"></script>



  



	





  





  








  <script src="//cdn1.lncld.net/static/js/3.0.4/av-min.js"></script>
  
  
  <script src="//unpkg.com/valine/dist/Valine.min.js"></script>
  
  <script type="text/javascript">
    var GUEST = ['nick','mail','link'];
    var guest = 'nick,mail';
    guest = guest.split(',').filter(function (item) {
      return GUEST.indexOf(item)>-1;
    });
    new Valine({
        el: '#comments' ,
        verify: false,
        notify: true,
        appId: 'zMDFLwV3WMlWrOYhJ7tOad3M-gzGzoHsz',
        appKey: 'cJDLxDoNgzq0JJUWQFmpCRdw',
        placeholder: '对这篇文章有什么看法？大胆地说出来吧',
        avatar:'wavatar',
        guest_info:guest,
        pageSize:'20' || 10,
    });
  </script>



  

  <script type="text/javascript">
    // Popup Window;
    var isfetched = false;
    var isXml = true;
    // Search DB path;
    var search_path = "search.xml";
    if (search_path.length === 0) {
      search_path = "search.xml";
    } else if (/json$/i.test(search_path)) {
      isXml = false;
    }
    var path = "/" + search_path;
    // monitor main search box;

    var onPopupClose = function (e) {
      $('.popup').hide();
      $('#local-search-input').val('');
      $('.search-result-list').remove();
      $('#no-result').remove();
      $(".local-search-pop-overlay").remove();
      $('body').css('overflow', '');
    }

    function proceedsearch() {
      $("body")
        .append('<div class="search-popup-overlay local-search-pop-overlay"></div>')
        .css('overflow', 'hidden');
      $('.search-popup-overlay').click(onPopupClose);
      $('.popup').toggle();
      var $localSearchInput = $('#local-search-input');
      $localSearchInput.attr("autocapitalize", "none");
      $localSearchInput.attr("autocorrect", "off");
      $localSearchInput.focus();
    }

    // search function;
    var searchFunc = function(path, search_id, content_id) {
      'use strict';

      // start loading animation
      $("body")
        .append('<div class="search-popup-overlay local-search-pop-overlay">' +
          '<div id="search-loading-icon">' +
          '<i class="fa fa-spinner fa-pulse fa-5x fa-fw"></i>' +
          '</div>' +
          '</div>')
        .css('overflow', 'hidden');
      $("#search-loading-icon").css('margin', '20% auto 0 auto').css('text-align', 'center');

      

      $.ajax({
        url: path,
        dataType: isXml ? "xml" : "json",
        async: true,
        success: function(res) {
          // get the contents from search data
          isfetched = true;
          $('.popup').detach().appendTo('.header-inner');
          var datas = isXml ? $("entry", res).map(function() {
            return {
              title: $("title", this).text(),
              content: $("content",this).text(),
              url: $("url" , this).text()
            };
          }).get() : res;
          var input = document.getElementById(search_id);
          var resultContent = document.getElementById(content_id);
          var inputEventFunction = function() {
            var searchText = input.value.trim().toLowerCase();
            var keywords = searchText.split(/[\s\-]+/);
            if (keywords.length > 1) {
              keywords.push(searchText);
            }
            var resultItems = [];
            if (searchText.length > 0) {
              // perform local searching
              datas.forEach(function(data) {
                var isMatch = false;
                var hitCount = 0;
                var searchTextCount = 0;
                var title = data.title.trim();
                var titleInLowerCase = title.toLowerCase();
                var content = data.content.trim().replace(/<[^>]+>/g,"");
                
                var contentInLowerCase = content.toLowerCase();
                var articleUrl = decodeURIComponent(data.url);
                var indexOfTitle = [];
                var indexOfContent = [];
                // only match articles with not empty titles
                if(title != '') {
                  keywords.forEach(function(keyword) {
                    function getIndexByWord(word, text, caseSensitive) {
                      var wordLen = word.length;
                      if (wordLen === 0) {
                        return [];
                      }
                      var startPosition = 0, position = [], index = [];
                      if (!caseSensitive) {
                        text = text.toLowerCase();
                        word = word.toLowerCase();
                      }
                      while ((position = text.indexOf(word, startPosition)) > -1) {
                        index.push({position: position, word: word});
                        startPosition = position + wordLen;
                      }
                      return index;
                    }

                    indexOfTitle = indexOfTitle.concat(getIndexByWord(keyword, titleInLowerCase, false));
                    indexOfContent = indexOfContent.concat(getIndexByWord(keyword, contentInLowerCase, false));
                  });
                  if (indexOfTitle.length > 0 || indexOfContent.length > 0) {
                    isMatch = true;
                    hitCount = indexOfTitle.length + indexOfContent.length;
                  }
                }

                // show search results

                if (isMatch) {
                  // sort index by position of keyword

                  [indexOfTitle, indexOfContent].forEach(function (index) {
                    index.sort(function (itemLeft, itemRight) {
                      if (itemRight.position !== itemLeft.position) {
                        return itemRight.position - itemLeft.position;
                      } else {
                        return itemLeft.word.length - itemRight.word.length;
                      }
                    });
                  });

                  // merge hits into slices

                  function mergeIntoSlice(text, start, end, index) {
                    var item = index[index.length - 1];
                    var position = item.position;
                    var word = item.word;
                    var hits = [];
                    var searchTextCountInSlice = 0;
                    while (position + word.length <= end && index.length != 0) {
                      if (word === searchText) {
                        searchTextCountInSlice++;
                      }
                      hits.push({position: position, length: word.length});
                      var wordEnd = position + word.length;

                      // move to next position of hit

                      index.pop();
                      while (index.length != 0) {
                        item = index[index.length - 1];
                        position = item.position;
                        word = item.word;
                        if (wordEnd > position) {
                          index.pop();
                        } else {
                          break;
                        }
                      }
                    }
                    searchTextCount += searchTextCountInSlice;
                    return {
                      hits: hits,
                      start: start,
                      end: end,
                      searchTextCount: searchTextCountInSlice
                    };
                  }

                  var slicesOfTitle = [];
                  if (indexOfTitle.length != 0) {
                    slicesOfTitle.push(mergeIntoSlice(title, 0, title.length, indexOfTitle));
                  }

                  var slicesOfContent = [];
                  while (indexOfContent.length != 0) {
                    var item = indexOfContent[indexOfContent.length - 1];
                    var position = item.position;
                    var word = item.word;
                    // cut out 100 characters
                    var start = position - 20;
                    var end = position + 80;
                    if(start < 0){
                      start = 0;
                    }
                    if (end < position + word.length) {
                      end = position + word.length;
                    }
                    if(end > content.length){
                      end = content.length;
                    }
                    slicesOfContent.push(mergeIntoSlice(content, start, end, indexOfContent));
                  }

                  // sort slices in content by search text's count and hits' count

                  slicesOfContent.sort(function (sliceLeft, sliceRight) {
                    if (sliceLeft.searchTextCount !== sliceRight.searchTextCount) {
                      return sliceRight.searchTextCount - sliceLeft.searchTextCount;
                    } else if (sliceLeft.hits.length !== sliceRight.hits.length) {
                      return sliceRight.hits.length - sliceLeft.hits.length;
                    } else {
                      return sliceLeft.start - sliceRight.start;
                    }
                  });

                  // select top N slices in content

                  var upperBound = parseInt('2');
                  if (upperBound >= 0) {
                    slicesOfContent = slicesOfContent.slice(0, upperBound);
                  }

                  // highlight title and content

                  function highlightKeyword(text, slice) {
                    var result = '';
                    var prevEnd = slice.start;
                    slice.hits.forEach(function (hit) {
                      result += text.substring(prevEnd, hit.position);
                      var end = hit.position + hit.length;
                      result += '<b class="search-keyword">' + text.substring(hit.position, end) + '</b>';
                      prevEnd = end;
                    });
                    result += text.substring(prevEnd, slice.end);
                    return result;
                  }

                  var resultItem = '';

                  if (slicesOfTitle.length != 0) {
                    resultItem += "<li><a href='" + articleUrl + "' class='search-result-title'>" + highlightKeyword(title, slicesOfTitle[0]) + "</a>";
                  } else {
                    resultItem += "<li><a href='" + articleUrl + "' class='search-result-title'>" + title + "</a>";
                  }

                  slicesOfContent.forEach(function (slice) {
                    resultItem += "<a href='" + articleUrl + "'>" +
                      "<p class=\"search-result\">" + highlightKeyword(content, slice) +
                      "...</p>" + "</a>";
                  });

                  resultItem += "</li>";
                  resultItems.push({
                    item: resultItem,
                    searchTextCount: searchTextCount,
                    hitCount: hitCount,
                    id: resultItems.length
                  });
                }
              })
            };
            if (keywords.length === 1 && keywords[0] === "") {
              resultContent.innerHTML = '<div id="no-result"><i class="fa fa-search fa-5x" /></div>'
            } else if (resultItems.length === 0) {
              resultContent.innerHTML = '<div id="no-result"><i class="fa fa-frown-o fa-5x" /></div>'
            } else {
              resultItems.sort(function (resultLeft, resultRight) {
                if (resultLeft.searchTextCount !== resultRight.searchTextCount) {
                  return resultRight.searchTextCount - resultLeft.searchTextCount;
                } else if (resultLeft.hitCount !== resultRight.hitCount) {
                  return resultRight.hitCount - resultLeft.hitCount;
                } else {
                  return resultRight.id - resultLeft.id;
                }
              });
              var searchResultList = '<ul class=\"search-result-list\">';
              resultItems.forEach(function (result) {
                searchResultList += result.item;
              })
              searchResultList += "</ul>";
              resultContent.innerHTML = searchResultList;
            }
          }

          if ('auto' === 'auto') {
            input.addEventListener('input', inputEventFunction);
          } else {
            $('.search-icon').click(inputEventFunction);
            input.addEventListener('keypress', function (event) {
              if (event.keyCode === 13) {
                inputEventFunction();
              }
            });
          }

          // remove loading animation
          $(".local-search-pop-overlay").remove();
          $('body').css('overflow', '');

          proceedsearch();
        }
      });
    }

    // handle and trigger popup window;
    $('.popup-trigger').click(function(e) {
      e.stopPropagation();
      if (isfetched === false) {
        searchFunc(path, 'local-search-input', 'local-search-result');
      } else {
        proceedsearch();
      };
    });

    $('.popup-btn-close').click(onPopupClose);
    $('.popup').click(function(e){
      e.stopPropagation();
    });
    $(document).on('keyup', function (event) {
      var shouldDismissSearchPopup = event.which === 27 &&
        $('.search-popup').is(':visible');
      if (shouldDismissSearchPopup) {
        onPopupClose();
      }
    });
  </script>





  

  
  <script src="https://cdn1.lncld.net/static/js/av-core-mini-0.6.4.js"></script>
  <script>AV.initialize("zMDFLwV3WMlWrOYhJ7tOad3M-gzGzoHsz", "cJDLxDoNgzq0JJUWQFmpCRdw");</script>
  <script>
    function showTime(Counter) {
      var query = new AV.Query(Counter);
      var entries = [];
      var $visitors = $(".leancloud_visitors");

      $visitors.each(function () {
        entries.push( $(this).attr("id").trim() );
      });

      query.containedIn('url', entries);
      query.find()
        .done(function (results) {
          var COUNT_CONTAINER_REF = '.leancloud-visitors-count';

          if (results.length === 0) {
            $visitors.find(COUNT_CONTAINER_REF).text(0);
            return;
          }

          for (var i = 0; i < results.length; i++) {
            var item = results[i];
            var url = item.get('url');
            var time = item.get('time');
            var element = document.getElementById(url);

            $(element).find(COUNT_CONTAINER_REF).text(time);
          }
          for(var i = 0; i < entries.length; i++) {
            var url = entries[i];
            var element = document.getElementById(url);
            var countSpan = $(element).find(COUNT_CONTAINER_REF);
            if( countSpan.text() == '') {
              countSpan.text(0);
            }
          }
        })
        .fail(function (object, error) {
          console.log("Error: " + error.code + " " + error.message);
        });
    }

    function addCount(Counter) {
      var $visitors = $(".leancloud_visitors");
      var url = $visitors.attr('id').trim();
      var title = $visitors.attr('data-flag-title').trim();
      var query = new AV.Query(Counter);

      query.equalTo("url", url);
      query.find({
        success: function(results) {
          if (results.length > 0) {
            var counter = results[0];
            counter.fetchWhenSave(true);
            counter.increment("time");
            
            counter.save(null, {
              success: function(counter) {
                
                  var $element = $(document.getElementById(url));
                  $element.find('.leancloud-visitors-count').text(counter.get('time'));
                
              },
              error: function(counter, error) {
                console.log('Failed to save Visitor num, with error message: ' + error.message);
              }
            });
          } else {
            
              var newcounter = new Counter();
              /* Set ACL */
              var acl = new AV.ACL();
              acl.setPublicReadAccess(true);
              acl.setPublicWriteAccess(true);
              newcounter.setACL(acl);
              /* End Set ACL */
              newcounter.set("title", title);
              newcounter.set("url", url);
              newcounter.set("time", 1);
              newcounter.save(null, {
                success: function(newcounter) {
                  var $element = $(document.getElementById(url));
                  $element.find('.leancloud-visitors-count').text(newcounter.get('time'));
                },
                error: function(newcounter, error) {
                  console.log('Failed to create');
                }
              });
            
          }
        },
        error: function(error) {
          console.log('Error:' + error.code + " " + error.message);
        }
      });
    }

    $(function() {
      var Counter = AV.Object.extend("Counter");
      if ($('.leancloud_visitors').length == 1) {
        addCount(Counter);
      } else if ($('.post-title-link').length > 1) {
        showTime(Counter);
      }
    });
  </script>



  

  
<script>
(function(){
    var bp = document.createElement('script');
    var curProtocol = window.location.protocol.split(':')[0];
    if (curProtocol === 'https') {
        bp.src = 'https://zz.bdstatic.com/linksubmit/push.js';        
    }
    else {
        bp.src = 'http://push.zhanzhang.baidu.com/push.js';
    }
    var s = document.getElementsByTagName("script")[0];
    s.parentNode.insertBefore(bp, s);
})();
</script>


  
  

  
  

  
    
      <script type="text/x-mathjax-config">
    MathJax.Hub.Config({
      tex2jax: {
        inlineMath: [ ['$','$'], ["\\(","\\)"]  ],
        processEscapes: true,
        skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
      },
      TeX: {equationNumbers: { autoNumber: "AMS" }}
    });
</script>

<script type="text/x-mathjax-config">
    MathJax.Hub.Queue(function() {
      var all = MathJax.Hub.getAllJax(), i;
        for (i=0; i < all.length; i += 1) {
          all[i].SourceElement().parentNode.className += ' has-jax';
        }
    });
</script>
<script type="text/javascript" src="//cdn.jsdelivr.net/npm/mathjax@2.7.5/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>

    
  


  
  
  
  <script src="/lib/needsharebutton/needsharebutton.js"></script>

  <script>
    
      pbOptions = {};
      
          pbOptions.iconStyle = "box";
      
          pbOptions.boxForm = "vertical";
      
          pbOptions.position = "bottomCenter";
      
          pbOptions.networks = "Weibo,Wechat,Douban,QQZone,Twitter,Facebook,GooglePlus,Evernote,Vkontakte";
      
      new needShareButton('#needsharebutton-postbottom', pbOptions);
    
    
  </script>

  

  
  
  
  <script src="/lib/pangu/dist/pangu.min.js?v=3.3"></script>
  <script type="text/javascript">pangu.spacingPage();</script>


  
  <script type="text/javascript" src="/js/src/js.cookie.js?v=6.3.0"></script>
  <script type="text/javascript" src="/js/src/scroll-cookie.js?v=6.3.0"></script>


  

  

  
  <style>
    .copy-btn {
      display: inline-block;
      padding: 6px 12px;
      font-size: 13px;
      font-weight: 700;
      line-height: 20px;
      color: #333;
      white-space: nowrap;
      vertical-align: middle;
      cursor: pointer;
      background-color: #eee;
      background-image: linear-gradient(#fcfcfc, #eee);
      border: 1px solid #d5d5d5;
      border-radius: 3px;
      user-select: none;
      outline: 0;
    }

    .highlight-wrap .copy-btn {
      transition: opacity .3s ease-in-out;
      opacity: 0;
      padding: 2px 6px;
      position: absolute;
      right: 4px;
      top: 8px;
    }

    .highlight-wrap:hover .copy-btn,
    .highlight-wrap .copy-btn:focus {
      opacity: 1
    }

    .highlight-wrap {
      position: relative;
    }
  </style>
  <script>
    $('.highlight').each(function (i, e) {
      var $wrap = $('<div>').addClass('highlight-wrap')
      $(e).after($wrap)
      $wrap.append($('<button>').addClass('copy-btn').append('Copy').on('click', function (e) {
        var code = $(this).parent().find('.code').find('.line').map(function (i, e) {
          return $(e).text()
        }).toArray().join('\n')
        var ta = document.createElement('textarea')
        document.body.appendChild(ta)
        ta.style.position = 'absolute'
        ta.style.top = '0px'
        ta.style.left = '0px'
        ta.value = code
        ta.select()
        ta.focus()
        var result = document.execCommand('copy')
        document.body.removeChild(ta)
        
          if(result)$(this).text('Copied')
          else $(this).text('Copy failed')
        
        $(this).blur()
      })).on('mouseleave', function (e) {
        var $b = $(this).find('.copy-btn')
        setTimeout(function () {
          $b.text('Copy')
        }, 300)
      }).append(e)
    })
  </script>


</body>
</html>
